递归全排列问题（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;
	}
}



  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
  
38
  
39
  
40
  
41
  
42
  
43
  
44
  
45
  
46
  
47
  
48
  
49
  
50
  
51
  
52
  
53
  
54
  
55
  
56
  
57
  
58
 

• 时间复杂度
  T ( n ) = { θ ( 1 ) n = 1 n T ( n − 1 ) + n n > 1 T(n) =
  {θ(1)nT(n−1)+nn=1n>1 $$\{\begin{array}{ll}\theta (1)& n=1\\ nT(n-1)+n& n>1\end{array}$$
  T(n)={θ(1)nT(n−1)+n​n=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; }
		}
	}
}

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
 

• 时间复杂度
  T ( n ) = { θ ( 1 ) n = 1 n T ( n − 1 ) + n n > 1 T(n) =
  {θ(1)nT(n−1)+nn=1n>1 $$\{\begin{array}{ll}\theta (1)& n=1\\ nT(n-1)+n& n>1\end{array}$$
  T(n)={θ(1)nT(n−1)+n​n=1n>1​

文章来源: ruochen.blog.csdn.net，作者：若尘，版权归原作者所有，如需转载，请联系作者。

原文链接：ruochen.blog.csdn.net/article/details/106257953