阶乘数系统与康托编码

摘要: 阶乘数系统、康托编码，全排列和字典序互相转换

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

---

在文章 回溯法的思想、设计与分析 中，我们系统学习了回溯法。回溯法将解空间看做树形结构，称为状态空间树，在文章 回溯法三种常见的状态空间树：子集树、排列树、满m叉树 中我们串讲了几种重要的状态空间树，排列树就是其中非常重要的一种。

利用回溯法，我们可以枚举全排列，有重复元素的全排列和无重复元素的全排列都可以枚举，参考文章 常见的枚举方式。

除了回溯法以外，还可以从两个全排列之间的关系出发，形成枚举全排列的算法：

• 将全排列抽象为图中的节点，那么 $n!$ 个全排列形成一个 $n!$ 节点的图，如果两个排列之间，是其中一个排列交换了相邻元素形成另一个排列的关系，我们认为这两个排列是相邻的，在图中相应的节点连边。可以证明，这样的图是哈密顿图，那么走一遍哈密顿路径自然就枚举了所有的全排列了，参考文章 SJT算法：沿哈密顿路径枚举全排列。
• 如果全排列的元素之间可以比较大小，那么排列之间就可以定义字典序，于是两个排列之间就有了大小关系，多个排列也可以进行排序。此时按照字典序走一遍，也可以枚举全排列，参考文章 字典序法枚举排列)。

本文我们以 60. 第k个排列 为模板题，看一下全排列和字典序排名之间如何互相转换，涉及到的算法是阶乘数系统和康托编码。康托展开可以作为排列的哈希函数，得到的字典序排名作为排列的哈希值使用，

问题：60. 第k个排列

给出集合 [1,2,3,…,n]，其所有元素共有 n! 种排列。

按大小顺序列出所有排列情况，并一一标记，当 n = 3 时, 所有排列如下：

• “123”
• “132”
• “213”
• “231”
• “312”
• “321”

提示：

1 <= n <= 9
1 <= k <= n!

给定 n 和 k，返回第 k 个排列。

示例 1：
输入：n = 3, k = 3
输出：”213”

示例 2：
输入：n = 4, k = 9
输出：”2314”

示例 3：
输入：n = 3, k = 1
输出：”123”

题解

算法1 : DFS + 剪枝

在回溯法中一个一个地找可行解（全排列），走到第 k 个可行解时，即可返回答案。

过程中可以增加剪枝，逻辑如下：

// 预处理阶乘
vector<int> factorials(n + 1, 1);
for(int i = 2; i <= n; ++i) factorials[i] = factorials[i - 1] * i;

// 已经选了 i 个数 还剩 n - i 个数，共 factorials[n - i] 种
if(deep + factorials[n - i] < k)
{
    deep += factorials[n - i];
    return false;
}

此剪枝非常有效

代码 (C++)

class Solution {
public:
    string getPermutation(int n, int k) {
        if(n == 1) return "1";
        vector<int> factorials(n + 1, 1);
        for(int i = 2; i <= n; ++i) factorials[i] = factorials[i - 1] * i;
        int result = 0;
        // 第0个一定是 '1'
        int path = 0;
        int state = 0;
        int deep = 0;
        dfs(deep, path, 0, result, k, n, state, factorials);
        return to_string(result);
    }

private:
    bool dfs(int& deep, int& path, int i, int& result, int k, int n, int& state, const vector<int>& factorials)
    {
        // 剪枝
        // 已经选了 i 个数 还剩 n - i 个数，共 factorials[n - i] 种
        if(deep + factorials[n - i] < k)
        {
            deep += factorials[n - i];
            return false;
        }
        // 已经产生 deep 个序列，当前序列已选 i 个数字
        if(i == n)
        {
            ++deep;
            if(deep == k)
            {
                result = path;
                return true;
            }
            else
                return false;
        }

        for(int j = 1; j <= n; ++j)
        {
            if(!(((1 << j) & state))) // 数字 j 没选
            {
                path = path * 10 + j;
                state |= (1 << j);
                if(dfs(deep, path, i + 1, result, k, n, state, factorials))
                    return true;
                path = (path - j) / 10;
                state &= ~(1 << j);
            }
        }
        return false;
    }
};

算法2: 阶乘数系统

阶乘数系统

阶乘数满足如下公式：

$$k = \sum\limits_{m=0}\limits^{N-1}k_{m}m! \quad 0 \leq k_{m} \leq m$$

即 k 的值等于其各个位上的数字乘以其阶乘数之和

排列与阶乘数系统的映射

n 位阶乘数有 $n!$ 个，对应 $n!$ 种排列。例如 6 个 3 位阶乘数：

从阶乘构造全排列

排列编号 0 ~ N!-1，对于给定编号 k，首先将其用阶乘数系统展开，从左到右各个系数的含义就是输入数组中已使用元素的索引，用后将其从输入数组中删掉。

例如 N = 3，输入为 [1,2,3]，k = 2, $k = 1 \times 2! + 0 \times 0! + 0 \times 0!$，系数为 (1,0,0)，求 k 对应的排列的过程如下：

• 看 (1,0,0) 的第 1 个元素 1，nums=[1,2,3], nums[1] = 2, 因此 item.push_back(2)，2 被使用，紧接着从 nums 删掉。
• 看 (1,0,0) 的第 2 个元素 0，nums=[1,3], nums[0] = 1, 因此 item.push_back(1)，1 被使用，紧接着从 nums 删掉。
• 看 (1,0,0) 的第 3 个元素 0，nums=[3], nums[0] = 3, 因此 item.push_back(3)，3 被使用，紧接着从 nums 删掉。

因此 k = 2 对应的排列为 213。

给定 k 输出全排列的算法(与康托编码一致)：输入为 n, k

构造 nums=[1,2,...,n]
while(!nums.empty())
    看 k 的阶乘数系统展开的第一项的系数 idx
    排列的下一位为 nums[idx]
    删除 nums[t]
    k -= idx * factorials[nums.size()]; // idx * 剩余nums长度的排列个数

以上算法的实现如下：

vector<int> nums(n, 0);
for(int i = 0; i < n; ++i) 
    nums[i] = i + 1;

for(int i = n - 1; i >= 0; --i) // 从高位往低位选
{
    int idx = k / factorials[i];
    k -= idx * factorials[i];
    ans = ans * 10 + nums[idx];
    nums.erase(nums.begin() + idx);
}

代码 (模板，C++)

• 用阶乘数系统给出字典序排名为 k 的 n 位全排列：

// 阶乘数系统
// 从高位往低位选
class Solution {
public:
    string getPermutation(int n, int k) {
        vector<int> nums(n, 0);
        for(int i = 0; i < n; ++i) nums[i] = i + 1;
        vector<int> factorials(n, 1);
        for(int i = 1; i < n; ++i) factorials[i] = factorials[i - 1] * i;

        // fit k in the invertal 0 .. (n! - 1)
        --k; // 从零计数
        int ans = 0;
        for(int i = n - 1; i >= 0; --i) // 从高位往低位选
        {
            int idx = k / factorials[i];
            k -= idx * factorials[i];
            ans = ans * 10 + nums[idx];
            nums.erase(nums.begin() + idx);
        }
        return to_string(ans);
    }
};

• 用阶乘数系统枚举无重复全排列：

class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int> > result;
        if(nums.empty()) return result;
        int n = nums.size();
        factorials = vector<int>(n + 1, 1);
        for(int i = 1; i <= n; ++i) factorials[i] = factorials[i - 1] * i;
        for(int k = 1; k <= factorials[n]; ++k)
        {
            vector<int> p = getPermutation(n, k);
            vector<int> item;
            for(int i: p) item.push_back((nums[i - 1]));
            result.push_back(item);
        }
        return result;
    }

private:
    vector<int> factorials;

    vector<int> getPermutation(int n, int k) {
        vector<int> nums(n, 0);
        for(int i = 0; i < n; ++i) nums[i] = i + 1;

        // fit k in the invertal 0 .. (n! - 1)
        --k; // 从零计数
        int ans = 0;
        for(int i = n - 1; i >= 0; --i) // 从高位往低位选
        {
            int idx = k / factorials[i];
            k -= idx * factorials[i];
            ans = ans * 10 + nums[idx];
            nums.erase(nums.begin() + idx);
        }
        vector<int> result;
        while(ans)
        {
            result.push_back(ans % 10);
            ans /= 10;
        }
        reverse(result.begin(), result.end());
        return result;
    }
};

算法3: 康托编码

康托展开是一个全排列到自然数的双射。常用于构建哈希表的空间压缩。

$$康托展开 \leftrightarrow 康托编码(逆康托展开)$$

• 康托展开：给定一个 n 位全排列，确定其是字典序的第几个全排列
• 逆康托展开：给定一个全排列的所有字符以及某个字典序号，得相应的全排列

给定全排列求字典序的过程

以 2341 为例，初始 rank = 0

• step1: 第 1 位是 2，即所有 1 开头的在前面，rank += 1 * 3! = 6
• step2: 第 2 位是 3，即所有以 1,2 作第 2 位的在前面，但是 2 已用，rank += 1 * 2! = 8
• step3: 第 3 位是 4，即所有以 1,2,3 作第 3 位的在前面，但是 1,2 已用，rank += 1 * 1! = 9
• step4: rank += 0 * 0! = 9

综上总结康托展开公式(rank 是从 0 开始计的。最后要加 1)：

康托展开公式与阶乘数系统的公式一致。

$$\begin{align} rank &= \sum\limits_{i=1}\limits^{n}order(a_{i})(n-i)! + 1 \\ \end{align}$$

$order(a_{i})$ 为 $a_{i+1}…a_{n}$ 中小于 $a_{i}$ 的个数。

代码模板 (C++)

vector<int> factorials(n + 1, 1);
for(int i = 2; i <= n; ++i) 
    factorials[i] = factorials[i - 1] * i;

int cantor_unfolds(const vector<int>& p)
{
    int n = p.size();
    int rank = 0;
    for(int i = 0; i < n; ++i)
    {
        int t = 0; // 
        for(int j = i + 1; j < n; ++j) // 这里可以线段树优化
            if(p[j] < p[i])
                ++t;
        rank += t * factorials[n - (i + 1)];
    }
    ++rank;
    return rank;
}

给定全排列求字典序的过程可以作为排列的哈希函数：

int cantor_unfolds(const vector<int>& p);

int hash(const vector<int>& p)
{
    return cantor_unfolds(p);
}

给定字典序求全排列的过程(康托编码)

康托展开公式与阶乘数系统的公式一致。因此算法与阶乘数系统一样。

对应上例，求字符集为 1234 的第 k=10 个全排列

• step0: --k; 变为从 0 开始
• step1: 9 / 3! 商 1 余 3, 首位选一个当前没用过的第2(商+1)小字符，即2，将2删除，134，k 更新为余数 3
• step2: 3 / 2! 商 1 余 1, 首位选一个当前没用过的第2(商+1)小字符，即3，将3删除，14，k 更新为余数 1
• step3: 1 / 1! 商 1 余 0, 首位选一个当前没用过的第2(商+1)小字符，即4，将4删除，1，k 更新为余数 0
• step4: 最后一位无需判断

代码模板 (C++)

康托编码的代码逻辑与阶乘数系统一致：

// fit k in the invertal 0 .. (n! - 1)
--k; // 从零计数
int ans = 0;
for(int i = n - 1; i >= 0; --i) // 从高位往低位选
{
    int idx = k / factorials[i];
    k -= idx * factorials[i];
    ans = ans * 10 + nums[idx];
    nums.erase(nums.begin() + idx);
}

---