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

喜欢ヅ旅行 2022-04-01 18:10 165阅读 0赞

在 [上一篇][Link 1]的方法一里，我们使用把数组的下标每次增加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个元素的全排列需要遍历 n n 次才能得到 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;
        for (int i = n + 1; i < s.Length; i++)
        {
            if (s[n].CompareTo(s[i]) >= 0)
                result++;
        }
        return result;
    }
    
    // 返回 input 的阶乘
    static int Factorial(int input)
    {
        int result = 1;
        for (int i = 2; i <= input; i++)
        {
            result = result * i;
        }
        return result;
    }

测试一下：

string[] s = new string[] { "A", "B", "C" };
    foreach (string[] p in Permutation2(s))
    {
        Console.WriteLine(p.Montage(t => t, " ") + " | " + X(p).ToString());
    }

Permutation2() 和 Montage() 函数请参考[上一篇][Link 1]。测试输出如下：  
A B C | 0  
A C B | 1  
B A C | 2  
B C A | 3  
C A B | 4  
C B A | 5  
  
**通过康托逆展开生成全排列**  
  
　　如果已知 s = \["A", "B", "C", "D"\]，X(s1) = 20，能否推出 s1 = \["D", "B", "A", "C"\] 呢？  
　　因为已知 X(s1) = a4\*3! + a3\*2! + a2\*1! + a1\*0! = 20，所以问题变成由 20 能否唯一地映射出一组 a4、a3、a2、a1？如果不考虑 ai 的取值范围，有  
3\*3! + 1\*2! + 0\*1! + 0\*0! = 20  
2\*3! + 4\*2! + 0\*1! + 0\*0! = 20  
1\*3! + 7\*2! + 0\*1! + 0\*0! = 20  
0\*3! + 10\*2! + 0\*1! + 0\*0! = 20  
0\*3! + 0\*2! + 20\*1! + 0\*0! = 20  
等等。但是满足 0 <= ai <= n-1 的只有第一组。可以使用辗转相除的方法得到 ai，如下图所示：  
![2011042422221712.png][]  
知道了a4、a3、a2、a1的值，就可以知道s1\[0\] 是子数组\["A", "B", "C", "D"\]中第3大的元素 "D"，s1\[1\] 是子数组 \["A", "B", "C"\] 中第1大的元素"B"，s1\[2\] 是子数组 \["A", "C"\] 中第0大的元素"A"，s\[3\] 是子数组 \["C"\] 中第0大的元素"C"，所以s1 = \["D", "B", "A", "C"\]。  
这样我们就能写出一个函数 Permutation3()，它可以返回 s 的第 m 个排列。

// 返回 s 的第 m 个排列（m 从 0 开始）。要求 s 是升序排列的
    static string[] Permutation3(string[] s, int m)
    {
        IList<string> sub = new List<string>(s);
        IList<string> result = new List<string>();
        for (int i = s.Length - 1; i >= 0; i--)
        {
            int f = Factorial(i);
            int ai = m / f;
            string item = sub[ai]; // 由于数组是升序排列的，所以第 ai 大的元素就是 sub[ai]
            result.Add(item);
            sub.RemoveAt(ai);
            m = m % f;
        }
        return result.ToArray();
    }

测试一下：

string[] s = new string[] { "A", "B", "C", "D" };
    for (int i = 0; i < Factorial(s.Length); i++)
    {
        string[] s1 = Permutation3(s, i);
        Console.WriteLine(s1.Montage(t => t, " "));
    }

**附录 康托展开是怎么来的？**  
  
　　很显然，康托展开是本文的关键所在。你说康托他老人家当初是怎么想出来这种展开的方法的呢？我们还是以 s=\["A", "B", "C"\] 为例：  
  
A B C | 0  
A C B | 1  
B A C | 2  
B C A | 3  
C A B | 4  
C B A | 5  
  
　　他的思路可能是这样的：首先，确定一个**目标**：将每个排列映射为一个自然数，这个自然数是顺序增长的（或者至少要有一定的规律）。要说映射成自然数，第一个想到的方法自然是把数组的下标当作一个n进制的数字，但是正如本文开篇所讨论的，这个数字并没有什么规律；第二个方法是**计数**，也就是令 X = 当前排列之前有多少个排列。例如 A B C 是第一个排列，它前面没有任何排列，所以 X(ABC) = 0；A C B 前面有一个排列，所以 X(ACB) = 1……那么如何才能知道 X(BCA) = 3 也就是 B C A 的前面有3个排列呢？这里的技巧仍然是**分解**——把问题分隔成**相互独立**的**有限**的小块。具体的方法是：先求出 B 第一次出现在最高位（也就是 B A C 这个排列）时前面有几个排列，再求出 B C A 是 B A C 后面第几个排列，把这个两个数相加就是想要的结果了。  
　　先看第一个问题：B 第一次出现在最高位（也就是 B A C 这个排列）时前面有几个排列？由于已知 B A C 前面的排列一定是 A 开头的，所以只有 A 后面的两个元素可以变化，所以排列数是 P(2,2) = 2! 个。  
　　第二个问题：B C A 是 B A C 后面第几个排列？因为都是 B 开头的，所以可以把开头的 B 忽略，问题变成 C A 是 A C 后面的第几个排列？同样，可以先考虑 C 第一次出现在最高位时前面有几个排列，因为 C A 前面的排列肯定是 A 开头的，所以只有 A 后面的一个元素可以变化，所以排列数是 P(1,1) = 1! 个。  
　　所以 X(BCA) = 2! + 1! = 3  
　　再例如想求 X(CBA)，同样是先考虑 C 第一次出现在最高位时前面有多少个排列，因为比 C 小的元素有 A 和 B 两个，所以是 2\*2! 个。再求出 B A 是 A B 后面的第 1! 个排列。就可以知道 X(CBA) = 2\*2! + 1! = 5 了。  
  
**感谢[徐少侠][Link 2]的帮助！**

**![o\_logo2\_170\_r.png][o_logo2_170_r.png]**

[Link 1]: http://www.cnblogs.com/1-2-3/archive/2011/04/17/generate-permutation-part1.html
[2011042422221712.png]: /images/20220401/4757fa0f4f34400080af8491f5fac84a.png
[Link 2]: http://www.cnblogs.com/Chinese-xu/
[o_logo2_170_r.png]: /images/20220401/e32cc19a86674a26a713e073d45223dc.png