康托展开和康托逆展开

Published on	7/29/2025
Created on	10/26/2021

康托展开

引入

康托展开（Cantor expansion）用于将排列转换为字典序的索引（逆展开则相反）百度百科维基百科

方法

假设我们要求排列 5 2 4 1 3 的字典序索引

逐位处理：

第一位：5 2 4 1 3，如果一个排列的第一位比 $5$ 小（有 $4$ 种情况）则不管其后 $4$ 位如何（有 $4!$ 种情况），其字典序都更小所以，至少有 $4\times 4!$ 个排列字典序更小。
第二位：5 2 4 1 3，如果另一个排列的第一位就是 $5$ ，但第二位比 $2$ 小（有 $1$ 种情况）则不管其后 $3$ 位如何（有 $3!$ 种情况），其字典序都更小所以，至少有 $4\times 4!+1\times 3!$ 个排列字典序更小。
第三位：~~5 2~~ 4 1 3，如果另一个排列的前两位与我们的相同，但第三位比 $4$ 小（ $2$ 不能选了，从右往左看，有 $2$ 种情况）则不管其后 $2$ 位如何（有 $2!$ 种情况），其字典序都更小所以，至少有 $4\times 4!+1\times 3!+2\times 2!$ 个排列字典序更小。
第四位：~~5 2 4~~ 1 3，如果另一个排列的前三位与我们的相同，但第四位比 $1$ 小（不可能，有 $0$ 种情况）则不管其后 $1$ 位如何（有 $1!$ 种情况），其字典序都更小所以，至少有 $4\times 4!+1\times 3!+2\times 2!+0\times1!$ 个排列字典序更小。
第五位：~~5 2 4 1~~ 3，按照上面的方法操作，很显然，有 $4\times 4!+1\times 3!+2\times 2!+0\times1!+0\times0!$ 个排列字典序更小。

因此，若索引从 $1$ 开始，则 5 2 4 1 3 的索引是 $4\times 4!+1\times 3!+2\times 2!+0\times1!+0\times0!+1=107$ 。

算法

总结上述方法，可以归纳出以下算法：

枚举排列的每一位，对值为 $p_k$ $p_{k}$ 的第 $k$ $k$ 位：
- 找出后面所有位（ $k+1$ 至 $n$ ）中小于 $p_k$ 的位数 $a_k$ （也就是 $p_k$ 是第 $k$ 至 $n$ 位第 $a_k+1$ 小的）

若用这些位中的某一位替换第 $k$ 位，则无论后面 $n-k$ 位如何排列（总共有 $a_k(n-k)!$ 种情况），最终的字典序肯定更小

把这些字典序更小的排列数加起来
再加 $1$ 即为该排列的字典序索引

公式

用公式来表示即为：

\mathrm{Index}(p)=1+\sum^n_{k=1} (n-k)! |\{p_i\mid p_i<p_k,\ k+1\leq i\leq n\}|

优化

其中 $a_k$ 的求值过程可以进行优化，设一序列 $P=\underbrace{[1,1,1,\dots,1]}_{n\text{个}1}$ 我们每处理一位就置 $P_{p_k}$ 为 $0$ 。这样在排列 $p$ 中，我们没处理过的值就可以被表示为序列 $P$ 中值为 $1$ 的索引，即：

\{p_i\mid k+1\leq i\leq n\}=\{i\mid P_i=1\}

我们可以用线段树、树状数组这样的数据结构来维护 $P$ ，要求小于 $p_k$ 的位数，即是求序列 $P$ 区间 $[1,p_k-1]$ 中 $1$ 的个数，这不就是区间求和吗？算法可以改进为以下这样：

优化算法

初始化长度为 $n$ （索引从 $1$ 开始），值全为 $1$ 的序列 $P$
枚举排列的每一位，对值为 $p_k$ $p_{k}$ 的第 $k$ $k$ 位：
- 修改 $P_{p_k}=0$
- 求出 $a=(n-k)!\sum^{p_k-1}_{i=1}P_i$ ，和式为序列 $P$ 区间 $[1,p_k-1]$ 的元素和
把所有 $a$ 相加，最后加 $1$ 即为索引。

时间复杂度为 $\mathrm{O}(n\log n)$

参考代码

题目：P5367 【模板】康托展开 - 洛谷（线段树版本 [[Segment Tree]]）

#include <cctype>
#include <cstdio>
#include <cstring>
#include <iostream>
//---//
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;

typedef unsigned int u;
typedef long long ll;
typedef unsigned long long llu;

#define rep(i, a, b) for (ll i = a; i < b; i++)
#define REP(i, a, b) for (ll i = a; i <= b; i++)
#define per(i, b, a) for (ll i = b; i >= a; i--)

const ll N = 1000005;
const ll mod = 998244353;

ll p[N], f[N], d[4 * N];
bool lz[4 * N];

#define mid ll m = s + ((t - s) >> 1)

void bd(ll s, ll t, ll i) {
  if (s == t) {
    d[i] = 1;
    return;
  }
  mid;
  bd(s, m, i * 2);
  bd(m + 1, t, i * 2 + 1);
  d[i] = (d[i * 2] + d[i * 2 + 1]) % mod;
}

void spr(ll s, ll t, ll i) {
  if (lz[i]) {
    d[2 * i] = 0;
    d[2 * i + 1] = 0;
    lz[2 * i] = true;
    lz[2 * i + 1] = true;
    lz[i] = false;
  }
}

void upd(ll l, ll r, ll s, ll t, ll i) {
  if (l <= s && t <= r) {
    d[i] = 0;
    lz[i] = true;
    return;
  }
  mid;
  spr(s, t, i);
  if (l <= m) upd(l, r, s, m, 2 * i);
  if (r > m) upd(l, r, m + 1, t, 2 * i + 1);
  d[i] = (d[i * 2] + d[i * 2 + 1]) % mod;
}

ll get(ll l, ll r, ll s, ll t, ll i) {
  if (l > r) return 0;
  if (l <= s && t <= r) return d[i];
  mid;
  spr(s, t, i);
  ll sum;
  if (l <= m) sum = get(l, r, s, m, 2 * i) % mod;
  if (r > m) sum = (sum + get(l, r, m + 1, t, 2 * i + 1)) % mod;
  return sum;
}

signed main() {
  ll n, r = 1;
  f[0] = 1;
  scanf("%lld", &n);
  bd(1, n, 1);
  REP(i, 1, n) scanf("%lld", &p[i]);
  REP(i, 1, n - 1) f[i] = f[i - 1] * i % mod;
  REP(k, 1, n) {
    upd(p[k], p[k], 1, n, 1);
    r = (r + get(1, p[k] - 1, 1, n, 1) * f[n - k] % mod) % mod;
  }
  printf("%lld", r);
}

// https://www.luogu.com.cn/record/60977896

参考

康托逆展开

引入

康托逆展开用于通过一个已知长度排列的字典序索引反求出该排列

推导

在[[康托展开]]中，我们知道了：

\mathrm{Index}(p)=1+\sum^n_{k=1}(n-k)!a_k

其中：

a_k=|\{p_i\mid p_i<p_k,\ k+1\leq i\leq n\}|

已知 $n$ 位排列 $p$ 的字典序索引为 $\mathrm{Index}(p)$ ，通过康托逆展开，我们可以求出各个 $a_i$ ，从而求出排列 $p$ 。首先，我们把右侧的 $1$ 移至左侧，再提出和式中的第一项：

\mathrm{Index}(p)-1=(n-1)!a_1+\sum^n_{k=2}(n-k)!a_k \quad(1)

好像我们能用整除直接求出 $a_1$ ，但我们得先证明后面那个和式不影响结果。由 $a_k$ 的定义，我们有 $a_k\leq n-k$ ，所以：

\begin{aligned} &\ \sum^n_{k=2}(n-k)!a_k\\ \leq &\ \sum^n_{k=2}(n-k)!(n-k)\\ = &\ \sum^n_{k=2}(n-k)!(n-k+1-1)\\ = &\ \sum^n_{k=2}(n-k+1)!-(n-k)!\\ = &\ \sum^{n-2}_{k=0}(k+1)!-k!\\ = &\ (n-1)!-1\\ < &\ (n-1)! \end{aligned}

把式 $(1)$ 右侧的和式看成带余除法的余数 $R_1$ ，原式写为：

\mathrm{Index}(p)-1=(n-1)!a_1+R_1\quad(R_1<(n-1)!)

把 $(n-1)!$ 看作除数， $a_1$ 看作商，我们就可以表示出 $a_1$ 了：

a_1=\lfloor\frac{\mathrm{Index}(p)-1}{(n-1)!}\rfloor

另外有

R_1=(\mathrm{Index}(p)-1)\ \%\ (n-1)!

我们继续拆出余下和式的第一项：

R_1=(n-2)!a_2+\sum^n_{k=3}(n-k)!a_k

这个式子和刚刚的是一模一样的，于是我们能同样地求出 $a_2$ 以及其他所有 $a$ 值，按照以下递推式：

\begin{aligned} a_i&=\lfloor\frac{R_{i+1}}{(n-i)!}\rfloor\\ R_i&=R_{i-1}\ \%\ (n-i)! \end{aligned}

这样，我们就求出了所有 $a$ ，回想一下， $a_k$ 是指排列的第 $k$ 位是排列第 $k$ 位至 $n$ 位（未处理的所有位）中第 $a_k+1$ 小的，我们只需从第 $1$ 位开始，对第 $i$ 位，从未选中的数中选择第 $a_i+1$ 小的添加到排列中，最后就能形成对应字典序的排列了。我们可以用一个初始化为[1,2,3,...,n]的vector，每处理一位则erase()一位，每次取索引为 $a_i$ 的元素即可。

算法

归纳上述推导过程就有了以下的算法：

初始化一个 $1$ 至 $n$ 的vector<int>vec
求出 $1$ 至 $n-1$ 的阶乘，备用
初始化 $R=\mathrm{Index}(p)-1$
对 $1$ $1$ 至 $n$ $n$ 的 $i$ $i$ 执行：
- 求出 $a=\lfloor\frac{R_{i+1}}{(n-i)!}\rfloor$
- 排列的 $p$ 的第 $i$ 位即为vec[a]
- 移除vec[a]
- 更新： $R\leftarrow R\ \%\ (n-i)!$
排列 $p$ 即为答案

参考代码

题目：P3014 [USACO11FEB]Cow Line S - 洛谷

#include <cctype>
#include <cstdio>
#include <cstring>
#include <iostream>
//---//
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;

typedef unsigned int u;
typedef long long ll;
typedef unsigned long long llu;

#define rep(i, a, b) for (ll i = a; i < b; i++)
#define REP(i, a, b) for (ll i = a; i <= b; i++)
#define per(i, b, a) for (ll i = b; i >= a; i--)

const ll N = 21;

ll p[N], f[N], d[4 * N];
vector<ll> vec;
bool lz[4 * N];

#define mid ll m = s + ((t - s) >> 1)

void bd(ll s, ll t, ll i) {
  lz[i] = false;
  if (s == t) {
    d[i] = 1;
    return;
  }
  mid;
  bd(s, m, i * 2);
  bd(m + 1, t, i * 2 + 1);
  d[i] = d[i * 2] + d[i * 2 + 1];
}

void spr(ll s, ll t, ll i) {
  if (lz[i]) {
    d[2 * i] = 0;
    d[2 * i + 1] = 0;
    lz[2 * i] = true;
    lz[2 * i + 1] = true;
    lz[i] = false;
  }
}

void upd(ll l, ll r, ll s, ll t, ll i) {
  if (l <= s && t <= r) {
    d[i] = 0;
    lz[i] = true;
    return;
  }
  mid;
  spr(s, t, i);
  if (l <= m) upd(l, r, s, m, 2 * i);
  if (r > m) upd(l, r, m + 1, t, 2 * i + 1);
  d[i] = d[i * 2] + d[i * 2 + 1];
}

ll get(ll l, ll r, ll s, ll t, ll i) {
  if (l > r) return 0;
  if (l <= s && t <= r) return d[i];
  mid;
  spr(s, t, i);
  ll sum;
  if (l <= m) sum = get(l, r, s, m, 2 * i);
  if (r > m) sum = sum + get(l, r, m + 1, t, 2 * i + 1);
  return sum;
}

signed main() {
  ll n, r, q, I, A;
  char c;
  f[0] = 1;
  scanf("%lld%lld\n", &n, &q);
  REP(i, 1, n - 1) f[i] = f[i - 1] * i;
  while (q--) {
    c = getchar();
    while (c != 'P' && c != 'Q') c = getchar();
    if (c == 'P') {
      scanf("%lld", &I);
      I--;
      REP(i, 1, n) vec.push_back(i);
      REP(i, 1, n) {
        A = I / f[n - i];
        I %= f[n - i];
        printf("%lld ", vec[A]);
        vec.erase(vec.begin() + A);
      }
      printf("\n");
    } else {
      r = 1;
      bd(1, n, 1);
      REP(i, 1, n) scanf("%lld", &p[i]);
      REP(k, 1, n) {
        upd(p[k], p[k], 1, n, 1);
        r += get(1, p[k] - 1, 1, n, 1) * f[n - k];
      }
      printf("%lld\n", r);
    }
  }
}

// https://www.luogu.com.cn/record/60986344