（参考：http://blog.csdn.net/zmazon/article/details/8351611）
这是从网上摘录的，经过一定的理解加工。
1.输出数组a的全排列(不可重复取)
如a={1,2,3}。输出123，132，213，231，312，321。这个是最基本，也是最经典的排列
算法思想：可以输出1加上23的全排列，2加13的全排列，3加上12的全排列，运用递归求比如23的全排列..依次递归下去；比如现在要2开头求全排，首先要交换1，2的位置，让a[0]变为2，在用递归求13的所有全排列，前面加个2就是2开头的所有全排列了，最后运用回溯再把1，2调换回来。
package cn.combine;
public class Arrange1 {
public void runPermutation(int[] a) {
getAllPermutation(a, 0);
}
/* index用于控制如上述分析中2加上13的所有全列的 */
public void getAllPermutation(int[] a, int index) {
/* 与a的元素个数相同则输出 */
if (index == a.length - 1) {
for (int i = 0; i < a.length; i++) {
System.out.print(a[i] + " ");//打印数组中所有元素
}
System.out.println();
return;
}
//每次打印前先交换一次，如第一次是a[0]与a[0]交换，然后打印出23的组合
//之后再交换回来，第二次先交换a[0]与a[1]，打印之后再还原数组
for (int i = index; i < a.length; i++) {
swap(a, index, i);
getAllPermutation(a, index + 1);
swap(a, index, i);
}
}
public void swap(int[] a, int i, int j) {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
public static void main(String[] args) {
Arrange1 robot = new Arrange1();
int[] a = { 1, 2, 3 };
robot.runPermutation(a);
}
}
说明：在理解递归的时候不能紧盯细小的部分，应该从大的范围理解，比如此处getAllPermutation的最后一个for循环，我们应该看到第一个交换是先后调换位置0和位置0的元素、调换位置0和位置1的元素、调换位置0和位置2的元素，每次调换后都是求剩下元素的组合，完了之后再通过调换将数组还原回来，于是从大的范围来看就是三次分别是1、2、3作为首元素首先打印出来，至于每次又打印剩余的我们不必细想。而作为递归结束的条件就是达到最后一个元素则开始的打印。
2.输出数组a的全排列(可重复取)
如a={1,2}。输出11,12,21,22
如果知道a的length，可以用暴力法求解(n的循环)
如果不知道a的length的情况下：
算法思想：用一个辅助空间b数组存储待输出的排列，用一个参数index记录一个排列的个数
package cn.combine;
public class Arrange2 {
public void runPermutation(int[] a) {
if (null == a || a.length == 0)
return;
int[] b = new int[a.length];// 辅助空间，保存待输出排列数
getAllPermutation(a, b, 0);
}
public void getAllPermutation(int[] a, int[] b, int index) {
//当index和数组的长度一致的时候打印
if (index == a.length) {
for (int i = 0; i < index; i++) {
System.out.print(b[i] + " ");
}
System.out.println();
return;
}
for (int i = 0; i < a.length; i++) {
b[index] = a[i];
getAllPermutation(a, b, index + 1);
}
}
public static void main(String[] args) {
Arrange2 robot = new Arrange2();
int[] a = { 1, 2, 3 };
robot.runPermutation(a);
}
}
说明：我们看方法getAllPermutation最后一个for循环，每次都是从0开始进行循环，第一次循环完成时数组b显然是[1,1,1]。而index作为一个结束递归的标记，当其值等于数组的长度的时候打印数组。
3.输出数组a的全排列(非递归)
如a={1,2,3}。输出123,132,213,231,312,321
全排列的非递归算法也不唯一，我写一个最常用的按字典序非递归算法。所谓字典序就是按照排列数的从大到小或从小到大输出，如123，132，2..，3...
算法思想：如果能按顺序输出序列是这个算法的核心，为了保证按顺序输出先对数组a进行排序。然后从后向前找到第一个顺序对（12是顺序对，21不是）标记为i，然后再从后面向前找到第一个比i大的数，记录为j，随后交换i,j对应的值，再逆序数组a[i+1]到a[length-1]。听到这里大家一定很迷糊，我们来举个例子，比如说2431这个数我们先在i，因为31是逆序，43是逆序，24是顺序，所以i=0；接着我们找j，第一个比2大的数是3，所以j=3，然后交换i，j变成（3，4，2，1）我们看看为什么要交换2,3？因为这个算法的核心思想是按字典序，而2431是以2开头的最大排列，下一个数就得是以3开头了（如果原数是2341按算法就是先要变成2431），接着3421这个数要进行i+1到length-1之间的逆序，变成3124，这个是2431的下一个数。所以可以看出交换后的数从下位开始到最后一定是一个逆序排列，所以逆序后才变成了相对的“最小值”。
package cn.combine;
import java.util.Arrays;
public class Arrange3 {
public void runNoRecursionOfPermutation(int[] a) {
Arrays.sort(a);// 对数组排序
while (true) {
printArray(a);// 输出一个排列
int i;// 从后向前，记录一对顺序值中的小值下标
int j;// 从后向前，记录比i大的第一个数
for (i = a.length - 2; i >= 0; i--) {
//找到第一个顺序的位置，比如1243，i便是1
if (a[i] < a[i + 1]){
break;
}else if (a[i] >= a[i + 1] && i == 0){
// 说明是最大逆序数退出函数，其实就是变成了一个最大的逆序数，如4321
//表示此时已经将全部组合输出完毕了
return;
}
}
//找到第一个比i位置数大的元素，这里注意后面的逆序中最后一个元素是最小的
for (j = a.length - 1; j > i; j--) {
if (a[j] > a[i])// 找到j跳出
break;
}
swap(a, i, j);// 交换i，j
reverse(a, i + 1, a.length - 1);// 翻转
}
}
public void swap(int[] a, int i, int j) {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
public void reverse(int[] a, int i, int j) {
while (i < j)
swap(a, i++, j--);
}
public void printArray(int[] a) {
for (int i = 0; i < a.length; i++) {
System.out.print(a[i] + " ");
}
System.out.println();
}
public static void main(String[] args) {
Arrange3 robot = new Arrange3();
int[] a = { 1, 2, 3 };
robot.runNoRecursionOfPermutation(a);
}
}
说明：这里我理解的不全，大致的想法就是这样输出
1234
1243
1324
1342
1423
1432
2134
...
可以看到当数序数12在前的时候，后面剩下的数就是从小到大输出，也就是从顺序变成逆序。
4.输出从数组a中取n个数的所有排列
如a={1,2,3} n=2输出12，21，13，31，23，32
这道题可以看作是排列组合的综合题，有关组合问题也可以参考我写的组合篇(http://blog.csdn.net/nash_/article/details/8315418)
算法思想：求出a中选取n个数的所有组合，分别对其进行全排列。
package cn.combine;
public class Arrange4 {
public void runPermutation(int[] a, int n) {
if (null == a || a.length == 0 || n <= 0 || n > a.length)
return;
int[] b = new int[n];// 辅助空间，保存待输出组合数
getCombination(a, n, 0, b, 0);
}
public void getCombination(int[] a, int n, int begin, int[] b, int index) {
if (n == 0) {// 如果够n个数了，输出b数组
getAllPermutation(b, 0);// 得到b的全排列
return;
}
//取n个数的所有情况
for (int i = begin; i < a.length; i++) {
b[index] = a[i];//取一个元素放到辅助数组中
//取剩下元素的组合
getCombination(a, n - 1, i + 1, b, index + 1);
}
}
//全排列
public void getAllPermutation(int[] a, int index) {
/* 与a的元素个数相同则输出 */
if (index == a.length - 1) {
for (int i = 0; i < a.length; i++) {
System.out.print(a[i] + " ");
}
System.out.println();
return;
}
for (int i = index; i < a.length; i++) {
swap(a, index, i);
getAllPermutation(a, index + 1);
swap(a, index, i);
}
}
public void swap(int[] a, int i, int j) {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
public static void main(String[] args) {
Arrange4 robot = new Arrange4();
int[] a = { 1, 2, 3, 4 };
int n = 3;
robot.runPermutation(a, n);
}
}
说明：这里我们可以这样理解，我们首先从4个数中取出3个，然后对取出的3个数进行全排列。全排列前面已经说明，这里我们看4选3。首先取一个数，然后递归去从剩下的3个元素中取2个，而停止条件就是取到3个的时候。注意：输入数据有重复类型：这类如a={1,3,2,3}， 3出现了两次，用以上排列会造成输出重复。
5.输出数组a的全排列(递归)
如a={1,1,2}输出112,121,211
算法思想：我们改进一下1的算法，在for中判断是否有包含重复元素，也就是index和i之间是否有和a[i]相等的值，比如对于2313这个数列，当index=0(a[index] = 2),i=3(a[i] = 3)的时候,如果要交换这两个数变成3312的话就是计算重复了，因为它们之间有1个3，当i=1的时候，它已经转换过3312了。所以加一个函数判断中间有没有包含重复元素，如有没有重复元素，再做交换。
package cn.combine;
public class Arrange5 {
public void runPermutation(int[] a) {
getAllPermutation(a, 0);
}
/* index用于控制如上述分析中2加上13的所有全列的 */
public void getAllPermutation(int[] a, int index) {
/* 与a的元素个数相同则输出 */
if (index == a.length - 1) {
for (int i = 0; i < a.length; i++) {
System.out.print(a[i] + " ");
}
System.out.println();
return;
}
for (int i = index; i < a.length; i++) {
if (contains(a, index, i))
continue;
swap(a, index, i);
getAllPermutation(a, index + 1);
swap(a, index, i);
}
}
public boolean contains(int[] a, int m, int n) {
for (int i = m; i < n; i++) {
if (a[i] == a[n])
return true;
}
return false;
}
public void swap(int[] a, int i, int j) {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
public static void main(String[] args) {
Arrange5 robot = new Arrange5();
int[] a = { 2, 3, 1, 3 };
robot.runPermutation(a);
}
}
说明：这里判断包含的时候我们可以这样理解，在全排列的时候我们每次选取一个数作为头，然后递归排列剩余的元素，当这个头输出所有排列情况之后就交换这个头和下一个元素，但是如果这两个要交换的元素中间有一个元素和i（要作为下一个头的元素位置）位置的元素相等，则会造成重复。比如2313，当i=1和i=3的情况实现相同的，和位置index交换后头都是3，也就是说不能有两次头为3的情况，所以后面一种情况我们需要删除。
6.从数组a中，取出n个数的所有组合(可重复取)
如a={1,2,3}。当n=2时候的所有组合数为11,12,13,22,23,33
算法思想：首先对数组a排序，再利用1的算法，把i=begin，改成i=0，让它每次从0开始遍历，但每个组合都是升序排列，所以为了去重加上升序的判断
package cn.combine;
import java.util.Arrays;
public class Arrange6 {
public void combine(int[] a, int n) {
if (null == a || a.length == 0 || n <= 0 || n > a.length)
return;
Arrays.sort(a);
int[] b = new int[n];// 辅助空间，保存待输出组合数
getCombination(a, n, 0, b, 0);
}
private void getCombination(int[] a, int n, int begin, int[] b, int index) {
if (n == 0) {// 如果够n个数了，输出b数组
for (int i = 0; i < index; i++) {
System.out.print(b[i] + " ");
}
System.out.println();
return;
}
for (int i = 0; i < a.length; i++) {
if (index == 0 || a[i] >= b[index - 1]) {
b[index] = a[i];
getCombination(a, n - 1, i + 1, b, index + 1);
}
}
}
public static void main(String[] args) {
Arrange6 robot = new Arrange6();
int[] a = { 1, 2, 3, 4 };
int n = 3;
robot.combine(a, n);
}
}
说明：这个例子较为容易理解，只是将之前的起始位置都换成0即可。
7、输入两个整数 n 和 m，从数列1，2，3.......n 中 随意取几个数，使其和等于 m ,要求将其中所有的可能组合列出来（不可重复取）
如m =5,n=4 输出14，23
这种问法是典型01背包问题，因为要求是输出所有组合，所以我们不用DP，而用回溯
算法思想：从最大数n开始尝试装包，输出所有情况，再尝试n不装包，输出所有情况。
package cn.combine;
public class Arrange7 {
public void combine(int m, int n) {
if (m < 1 || n < 1)
return;
if (n > m)// 如果n>m,把n>m的数去掉
n = m;
boolean[] b = new boolean[n + 1];// 保存是否装包
getCombination(m, n, b);
}
public void getCombination(int m, int n, boolean[] b) {
if (m < 1 || n < 1)// 递归出口
return;
//重量和容量相等
if (m == n) {// 输出组合
b[n] = true;//这里我们将物品装入背包中
//将放入包中的都打印出来
for (int i = 1; i < b.length; i++) {
if (b[i] == true)
System.out.print(i + " ");
}
System.out.println();
}
b[n] = true;// 装包
getCombination(m - n, n - 1, b);
b[n] = false;// 不装包
getCombination(m, n - 1, b);
}
public static void main(String[] args) {
Arrange7 robot = new Arrange7();
robot.combine(10, 12);
}
}
说明：这里是使用的回溯法解决此问题。
