全排列问题的解题思路

假设有这么个正整数n要求输出1到n的所有排列
 
输入3
输出123132213231312321

一、无脑循环求解

拿到这个问题当然我的第一个想法就是 for 循环比如这样

for(int i = 1; i < n+1; i++){
	for(int j = 1; j < n+1; j++){
		for(int k = 1; k < n+1; k++){
			……从此陷入无尽的循环
		}
	}
}

可是问题大了循环到底有多少个n 个

又或者是 while 循环来控制循环次数

while(i < n){
	for(int j = 1; j < n+1; j++){
		……就这样又陷入循环
	}
	i++;
}

其实如果了解回溯算法也不至于拿个 for 循环来为难自己下面就来分析一下这个问题。

二、全排列的个数

首先关于这个全排列问题很容易就能得到问题的答案个数为 n个

当 n = 2 时全排列的个数为 2 个

[1,2]、[2,1]

当 n = 3 时全排列的个数为 3*2 即 6 个

[1,2,3]、[1,3,2]、[2,1,3]、[2,3,1]、[3,1,2]、[3,2,1]

当 n = 4 时全片列的个数为 4*3*2 即 24 个

[1, 2, 3, 4]、[1, 2, 4, 3]、[1, 3, 2, 4]、[1, 3, 4, 2]、[1, 4, 2, 3]、[1, 4, 3, 2]、
[2, 1, 3, 4]、[2, 1, 4, 3]、[2, 3, 1, 4]、[2, 3, 4, 1]、[2, 4, 1, 3]、[2, 4, 3, 1]、
[3, 1, 2, 4]、[3, 1, 4, 2]、[3, 2, 1, 4]、[3, 2, 4, 1]、[3, 4, 1, 2]、[3, 4, 2, 1]、
[4, 1, 2, 3]、[4, 1, 3, 2]、[4, 2, 1, 3]、[4, 2, 3, 1]、[4, 3, 1, 2]、[4, 3, 2, 1]

很容易推出 n 个数字时全排列的个数为 n! 个。

三、回溯算法解题

接下来就利用回溯算法来解决这个问题还是比较简单的。首先我们需要构建全排列的解空间。同样这里先研究规模较小的问题假设 n 为 3 时的解空间

回溯算法的解空间就是一颗多叉树通常根节点为空。这这颗多叉树中叶子结点被称为不可扩展的结点非叶子结点称为可扩展结点。

接下来就需要通过深度遍历来遍历这颗多叉树每次遍历至叶子结点就可以得到一个相应的解。

回溯就发生在遍历的过程中当遇到不可扩展的结点时就需要回溯到树的上一层继续遍历其他可扩展结点。

接下来就可以用代码来实现了主要有两种方式来实现回溯算法

1、递归实现回溯算法

  递归实现思路函数自调通过自调函数来不断向树的深处进行遍历而通过 for 循环来找到合适的结点并暂存在结果集中。递归终止时即获得一个完整的结果

/**
 * 
 * @param t 	起始层数初始值为 1
 * @param n		数的个数也是树的最后一层
 * @param ls	结果集
 */
public static void backTrack(int t, int n, ArrayList<Integer> ls) {
		if(t > n) {
			System.out.println(ls.toString());
		}else {
			for(int i = 1; i < n+1; i++) {
				if(ls.contains(i))
					continue;
				else
					ls.add(i);
				backTrack(t+1, n, ls);
				ls.remove(t-1);
			}

		}
}

下面是递归调用的抽象过程

观察这个过程你会发现递归对于回溯算法是具有天生的优势的或者说递归就是一个不断回溯的过程而迭代实现回溯算法是比较难以理解的。

2、迭代实现回溯算法

  递归实现思路使用迭代来实现回溯就像一头扎进死胡同然后再一步一步回退回退之后再扎进死胡同。直到回退到胡同外即退出整个回溯过程。

/**
 * @param n 	数的个数
 * @param ls	结果集
 */
public static void iterativeBacktrack(int n, ArrayList<Integer> ls) {
		int t = 1;
		int left = 1;
		while(t > 0) {
			if(left <= n) {
				for(int i = left; i <= n; i++) {
					if(ls.contains(i)) {
						continue;
					}else {
						if(ls.size() == t){
							ls.set(t-1, i);
						}else{
							ls.add(t-1, i);
						}
						i = 0;
					}
					if(t == n) {
						System.out.println(ls.toString());
					}else {
						t++;
						i=0;
					}
				}
			}
			if (t > 0){
				ls.remove(t-1);
			}
			t--;
			if(t > 0)
				left = ls.get(t-1);
		}
}

---

其实回溯算法还有最后一步通过约束条件和边界控制来剪去多余的枝干以提升回溯算法的效率。 这里就不进行剪枝了……