1.6 字符串的全排列

void CalcAllPermutation(char* perm, int from, int to)
{
	if (to <= 1)
	{
		return;
	}

	if (from == to)
	{
		for (int i = 0; i <= to; i++)
			cout << perm[i];
		cout << endl;
	}
	else
	{
		for (int j = from; j <= to; j++)
		{
			swap(perm[j], perm[from]);
			CalcAllPermutation(perm, from + 1, to);
			swap(perm[j], perm[from]);
		}
	}
}

解法二、字典序排列

首先，咱们得清楚什么是字典序。根据维基百科的定义：给定两个偏序集A和B,(a,b)和(a′,b′)属于笛卡尔集 A × B，则字典序定义为

(a,b) ≤ (a′,b′) 当且仅当 a < a′ 或 (a = a′ 且 b ≤ b′)。

所以给定两个字符串，逐个字符比较，那么先出现较小字符的那个串字典顺序小，如果字符一直相等，较短的串字典顺序小。例如：abc < abcd < abde < afab。

那有没有这样的算法，使得

• 起点： 字典序最小的排列, 1-n , 例如12345
• 终点： 字典序最大的排列，n-1, 例如54321
• 过程： 从当前排列生成字典序刚好比它大的下一个排列

答案是肯定的：有，即是STL中的next_permutation算法。

在了解next_permutation算法是怎么一个过程之前，咱们得先来分析下“下一个排列”的性质。

• 假定现有字符串(A)x(B)，它的下一个排列是：(A)y(B’)，其中A、B和B’是“字符串”(可能为空），x和y是“字符”，前缀相同，都是A，且一定有y > x。
• 那么，为使下一个排列字典顺序尽可能小，必有：
• A尽可能长
• y尽可能小
• B’里的字符按由小到大递增排列

现在的问题是：找到x和y。怎么找到呢？咱们来看一个例子。

比如说，现在我们要找21543的下一个排列，我们可以从左至右逐个扫描每个数，看哪个能增大（至于如何判定能增大，是根据如果一个数右面有比它大的数存在，那么这个数就能增大），我们可以看到最后一个能增大的数是：x = 1。

而1应该增大到多少？1能增大到它右面比它大的那一系列数中最小的那个数，即：y = 3，故此时21543的下一个排列应该变为23xxx，显然 xxx(对应之前的B’）应由小到大排，于是我们最终找到比“21543”大，但字典顺序尽量小的23145，找到的23145刚好比21543大。

由这个例子可以得出next_permutation算法流程为：

next_permutation算法

• 定义

• 升序：相邻两个位置ai < ai+1，ai 称作该升序的首位

• 步骤（二找、一交换、一翻转）

• 找到排列中最后（最右）一个升序的首位位置i，x = ai

• 找到排列中第i位右边最后一个比ai 大的位置j，y = aj

• 交换x，y

• 把第(i+ 1)位到最后的部分翻转

还是拿上面的21543举例，那么，应用next_permutation算法的过程如下：

• x = 1；
• y = 3
• 1和3交换
• 得23541
• 翻转541
• 得23145

23145即为所求的21543的下一个排列。参考实现代码如下：

bool CalcAllPermutation(char* perm, int num){
	int i;

	//①找到排列中最后（最右）一个升序的首位位置i，x = ai
	for (i = num - 2; (i >= 0) && (perm[i] >= perm[i + 1]); --i){
		;
	}
	// 已经找到所有排列
	if (i < 0){
		return false;
	}

	int k;
	//②找到排列中第i位右边最后一个比ai 大的位置j，y = aj
	for (k = num - 1; (k > i) && (perm[k] <= perm[i]); --k){
		;
	}

	//③交换x，y
	swap(perm[i], perm[k]);
	//④把第(i+ 1)位到最后的部分翻转
	reverse(perm + i + 1, perm + num);
	return true;
}