白话算法(7) 生成全排列的几种思路(二) 康托展开
在html" target=_blank>上一篇的方法一里，我们使用把数组的下标每次增加1的方法得到重复的全排列，然后再挑出不重复的全排列。如下图所示，绿颜色表示想要得到的结果。
0 0 0
0 0 1
0 0 2
0 1 0
0 1 1
0 1 2
0 2 0
0 2 1
0 2 2
1 0 0
1 0 1
1 0 2
1 1 0
1 1 1
1 1 2
1 2 0
1 2 1
1 2 2
2 0 0
2 0 1
2 0 2
2 1 0
2 1 1
2 1 2
2 2 0
2 2 1
2 2 2
这种方法虽然简单，但是效率比较差。要生成n个元素的全排列需要遍历 nn 次才能得到 n! 个解（看上面那个绿色和黑色的下标的比例也可以有一个直观的感觉）。能不能直接把当前排列增加 i 得到下一个排列呢？例如，把 012 增加 2 得到 021 （按 3 进制计算），把 021 增加 4 得到 102……把 201 增加 2 得到 210？可以看到，有时候是增加 2，有时候是增加 4，很难摸清其中的规律（如果想求 [1,2,3,4] 的全排列，会发现有时候需要增加 3，有时候需要增加 6，有时候需要增加 9，甚至有时候需要增加 21）。这里的难点是，把数字增加 i 之后，可能会发生一连串的进位，而你很难知道这一连串的进位之后，哪两个位上的数字会重复。当问题的变量很多，而这些变量又相互影响时，问题就会变得复杂而难以解决。要想简化问题，就必须找到一个一致的方法表达这些相互影响的变量对结果的影响。把多个维度叠加到一个维度之上，是简化问题的常用手段。譬如，能否找到一个一致的方法把全排列映射为一个每次增加1的序列呢？ 也就是：
[0,1,2] => 0
[0,2,1] => 1
[1,0,2] => 2
[1,2,0] => 3
[2,0,1] => 4
[2,1,0] => 5
这样给出[2,0,1]就可以知道它是第5个排列了；反过来，根据这种独特的映射方法，也有可能知道第5个排列是[2,0,1]。这个映射可以使用康托展开来实现。
康托展开
康托展开的公式是 X=an*(n-1)!+an-1*(n-2)!+...+ai*(i-1)!+...+a2*1!+a1*0! 其中，ai为当前未出现的元素中是排在第几个（从0开始）。
这个公式可能看着让人头大，最好举个例子来说明一下。例如，有一个数组 s = ["A", "B", "C", "D"]，它的一个排列 s1 = ["D", "B", "A", "C"]，现在要把 s1 映射成 X。n 指的是数组的长度，也就是4，所以
X(s1) = a4*3! + a3*2! + a2*1! + a1*0!
关键问题是 a4、a3、a2 和 a1 等于啥？
a4 = "D" 这个元素在子数组 ["D", "B", "A", "C"] 中是第几大的元素。"A"是第0大的元素，"B"是第1大的元素，"C" 是第2大的元素，"D"是第3大的元素，所以 a4 = 3。
a3 = "B" 这个元素在子数组 ["B", "A", "C"] 中是第几大的元素。"A"是第0大的元素，"B"是第1大的元素，"C" 是第2大的元素，所以 a3 = 1。
a2 = "A" 这个元素在子数组 ["A", "C"] 中是第几大的元素。"A"是第0大的元素，"C"是第1大的元素，所以 a2 = 0。
a1 = "C" 这个元素在子数组 ["C"] 中是第几大的元素。"C" 是第0大的元素，所以 a1 = 0。（因为子数组只有1个元素，所以a1总是为0）
所以，X(s1) = 3*3! + 1*2! + 0*1! + 0*0! = 20
康托展开的C#代码如下：
static long X(string[] s) |
for (int i = 0; i < len; i++) |
result += An(s, i) * Factorial(len - i - 1); |
static int An(string[] s, int n) |
