递归全排列问题（两种方法 Java实现）

太过爱你忘了你带给我的痛 2023-02-11 03:19 1阅读 0赞

###  ###

*  递归全排列问题（Java实现）
 *   *  问题描述
     *  算法
     *   *  1. 固定位置放元素
         *  2. 固定元素找位置

# 递归全排列问题（Java实现） #

## 问题描述 ##

*  生成 \{1,2,…,n\} 的所有 n! 个排列

## 算法 ##

### 1. 固定位置放元素 ###

--------------------

*  算法思想
    
     *  生成元素\{2,3,…,n\}的所有排列，并且将元素1放到每个排列的开头
     *  生成元素\{1,3,…,n\}的所有排列，并将数字2放到每个排列的开头
     *  重复这个过程，直到元素\{2,3,…,n-1\}的所有排列都产生，并将元素n放到每个排列的开头
 *  Java源代码

/* * 若尘 */
    package perm;
    
    import java.util.Arrays;
    
    /** * 全排列问题（递归） * @author ruochen * @version 1.0 */
    public class GeneratiingPerm { 
    
    	public static int count = 0;
    	
    	public static void main(String[] args) { 
    		char[] arr = { 'a', 'b', 'c'};
    		int start = 0;
    		int end = arr.length - 1;
    		perm(arr, start, end);
    		System.out.println("共有 " + count + " 种排列方式");
    	}
    	
    	/** * 实现全排列 * @param arr 待求全排列数组 * @param start 开始位置 * @param end 结束位置 */
    	public static void perm(char[] arr, int start, int end) { 
    		if (start == end) { 
    			count++;
    			System.out.println(Arrays.toString(arr));
    		} else { 
    			for (int i = start; i <= end; i++) { 
    				swap(arr, start, i);
    				perm(arr, start + 1, end);
    				// 为了排列不会丢失，我们这里在交换回来，使得每次都是以一个固定序列开始
    				swap(arr, start, i);
    			}
    		}
    	}
    	
    	/** * 交换两个数组元素 * @param arr 数组 * @param i 第一个元素下标 * @param j 第二个元素下标 */
    	public static void swap(char[] arr, int i, int j) { 
    		char temp = arr[i];
    		arr[i] = arr[j];
    		arr[j] = temp;
    	}
    }

*  时间复杂度  
     T ( n ) = \{ θ ( 1 ) n = 1 n T ( n − 1 ) + n n > 1 T(n) = \\begin\{cases\} θ(1) & n = 1 \\\\ nT(n - 1) + n & n > 1 \\\\ \\end\{cases\} T(n)=\{ θ(1)nT(n−1)\+nn=1n>1

### 2. 固定元素找位置 ###

*  算法思想
    
    1.  首先，我们把 n 放在的位置P\[1\]上，并且用子数组P\[2…n\]来产生前n-1个数的排列
    2.  接着，我们将 n 放在P\[2\]上，并且用子数组P\[1\]和P\[3…n\]来产生前n-1个数的排列
    3.  然后，我们将 n 放在P\[3\]上，并且用子数组P\[1…2\]和P\[4…n\]来产生前n-1个数的排列
    4.  重复上述过程直到我们将 n 放在P\[n\]上，并且用子数组P\[1…n\]来产生前n-1个数的排列
 *  Java源代码

public static void perm2(char[] arr, int start, int end) { 
    	if (end == 0) { 
    		System.out.println(Arrays.toString(arr));
    	} else { 
    		for (int i = start; i <= end; i++) { 
    			if (arr[i] == 0) { 
    				arr[i] = (char) end;
    				perm2(arr, start, end - 1);
    				arr[i] = 0;
    			}
    		}
    	}
    }

*  时间复杂度  
     T ( n ) = \{ θ ( 1 ) n = 1 n T ( n − 1 ) + n n > 1 T(n) = \\begin\{cases\} θ(1) & n = 1 \\\\ nT(n - 1) + n & n > 1 \\\\ \\end\{cases\} T(n)=\{ θ(1)nT(n−1)\+nn=1n>1