By

文章目录
  1. 1. 全排列
  2. 2. 全组合
  3. 3. 参考

全排列

这里主要使用递归来实现，也就是考察递归的熟练使用与否

全排列的递归生成规则为：

  1. n个数的全排列=(其中一个数的前缀)+n-1个树的全排列
  2. 当前只剩下一个待选前缀的时候，停止迭代
  3. 关于前缀的设立，是逐个迭代剩余的候选元素通过两两交换完成的，在进行输出之后还需要还得将两个数字重新交换回去
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
/**
 * 全排列算法
 * 依次将剩余的元素交换到begin处  直到end的地方进行输出
 * @param a
 * @param begin
 * @param end
 */
public static void permutation(int[] a,int begin,int end)
{
	if(begin==end)//当前已经排列完成 进行输出
	{
		for(int i=0;i<a.length;i++)
			System.out.print(a[i]);
		System.out.println();
	}else{
		for(int j=begin;j<=end;j++)
		{
			swap(a,begin,j);//依次遍历剩余元素放置在begin 位置处
			permutation(a,begin+1,end);
			swap(a,begin,j);//将之前交换的数据还原
		}
	}
}

public static void swap(int[] a,int i,int j)
{
	int temp=a[i];
	a[i]=a[j];
	a[j]=temp;
}

进行测试输出为：

1
2
int[] a={1,2,3};
permutation(a,0,a.length-1);

最终的结果是

123
132
213
231
321
312

这里，这里只考虑的无重复的情况，一旦有重复的，需要考虑去重，因为两个相同的数字交换没什么意思啊。这里的去重主要是在for循环中添加一个isSwap来判断是否要交换即可。

全组合

全组合貌似就是一个元素的全子集算法，之前做过的-_-

参考

本作品采用[知识共享署名-非商业性使用-相同方式共享 2.5]中国大陆许可协议进行许可，我的博客欢迎复制共享，但在同时，希望保留我的署名权

文章目录
  1. 1. 全排列
  2. 2. 全组合
  3. 3. 参考