全排列之康托编码(附 Java版代码)

• 引言：

最近准备校招，开始重拾算法，开启leetcode刷题之旅。刷到#60 Permutation Sequence 一题，憋了半天，开始Google，于是发现一个新奇的算法——康托编码。

康托展开：全排列到一个自然数的双射

X=an!+an-1!+…+ai!+…+a[1]0! ，其中a[i]为当前未出现的元素中是排在第几个（从0开始）。这就是康托展开。康托展开可用代码实现。
(使用范围：没有重复元素的全排列)

全排列的编码

{1,2,3,4,…,n}的排列总共有n!种，将它们从小到大排序，怎样知道其中一种排列是有序序列中的第几个？
如：{1, 2, 3}的数组按照从小到大的全排列为：123, 132, 213, 231, 312, 321。现在，要知道231是第几大的数。
分析如下：第一位是2，比2小的数有1，第一位是1的全排列个数是 2! 个，故由第一位能确定 1 × 2! = 2 个比 231 小的数；第二位是3，比 3 小的数有1、2，而2在第一位，故由前两位确定的比231小的数有 1 × 1! = 1 个；最后1位为1，1小的数有0个。最终确定的比231小的数的个数为1 × 2! + 1 × 1! = 3 个，而231为第4大的数。

再举个列子：
1324是{1, 2, 3, 4}排列数中第几大的数：第一位为1,小于1的数有0个，故为0 × 3! = 0个；第二位为3，小于3的数有1、2，其中1在第一位，故为1 × 2! = 2 个；第三位为2，小于2的数有1，而1在第一位，故为 0 × 1! = 0 个；第四位为4，小于4的数有1、2、3，而1在第一位，3在第二位，2在第三位，故为0 × 0! = 0个；所以比1324小的排列有0 3! + 1 2! + 0 1! + 0 0! = 2 个，而1324是第三大的数。
又例如，排列2 6 3 8 1 4 9 7 5展开为61683，因为X=1 8! + 4 7! + 1 6! + 4 5! + 0 4! + 0 3! + 2 2! + 1 1! = 61683.

Java实现如下：

/**
 * 计算给定数是全排列中第几大的数
 * @param n 全排列位数
 * @param m 给定的数
 * @return
 */
public int KT(int n, int m) {
    String mStr = String.valueOf(m);
    int result = 1;
    if (n < 2) return result;

    int[] level = new int[n + 1];  // 缓存阶乘结果
    level[0] = 1;
    for (int i = 1; i <= n; i++) level[i] = level[i - 1] * i;

    // 康托计算
    boolean[] flag = new boolean[n + 1];
    for (int i = 0; i < n; i++) {
        int cur = mStr.charAt(i) - '0';
        int count = cur - 1;
        for (int j = 1; j < cur; j++) {
            if (flag[j]) count--;
        }
        flag[cur] = true;
        result += count * level[n - i - 1];
    }
    return result;
}

全排列的解码

如何找出第16个（按字典序的）{1,2,3,4,5}的全排列？
过程如下：

首先用16-1得到15
用15去除4! 得到0余15
用15去除3! 得到2余3
用3去除2! 得到1余1
用1去除1! 得到1余0
有0个数比它小的数是1，所以第一位是1
有2个数比它小的数是3，但1已经在之前出现过了所以是4
有1个数比它小的数是2，但1已经在之前出现过了所以是3
有1个数比它小的数是2，但1,3,4都出现过了所以是5
最后一个数只能是2

所以排列为1 4 3 5 2

Java实现如下：

/**
 * 给定全排列位数和数字K，返回全排列中第 K 大的数
 * @param n 全排列位数
 * @param k 给定的数K
 * @return
 */
public int Cantor(int n, int k) {
    if (n < 1) return -1;

    int[] level = new int[n];  // 缓存阶乘结果
    level[0] = 1;
    for (int i = 1; i < n; i++) {
        level[i] = level[i - 1] * i;
    }

    int result = 0;
    boolean[] flag = new boolean[n + 1];
    k--;
    for (int i = 0; i < n; i++) {
        int cur = k / level[n - i - 1];
        int j = 1;
        // 从头开始找到 cur 个坑位为尚未填写的数字
        for (; j <= n; j++) {
            if (!flag[j]) {
                if (cur == 0)   break;
                --cur;
            }
        }
        flag[j] = true;
        result = result * 10 + j;
        k = k % level[n - i - 1];
    }

    return result;
}