首页 > 程序开发 > 综合编程 > 其他综合 >

白话算法(7) 生成全排列的几种思路(二) 康托展开

2011-05-24

在上一篇的方法一里,我们使用把数组的下标每次增加1的方法得到重复的全排列,然后再挑出不重复的全排列。如下图所示,绿颜色表示想要得到的结果。0 0 00 0 10 0 20 1 00 1 10 1 20 2 00 2 10 2 21 0 01 0 11 0 21 1 01 1 11 1 21 2 01 2

上一篇的方法一里,我们使用把数组的下标每次增加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#代码如下:
// 返回s的康托展开值
static long X(string[] s)
{
long result = 0;
int len = s.Length;
for (int i = 0; i < len; i++)
{
result += An(s, i) * Factorial(len - i - 1);
}
return result;
}
// 返回 s[n] 是 s[n..length] 中第几大的元素
static int An(string[] s, int n)
{
int result = 0;
热点推荐