康托展开Cantor expansion 康托逆展开

康托展开

定义

对于n位数的某个排列s[0,n-1],有

X=a[n]∗n−1)!+a[n−1]∗n−2)!+...+a[i]∗i−1)!+...+a[1]∗0!

X 为 s 在整个全排列中的位置－1
a[i] 表示在i位后面出现的小于s[i]的数 的个数

解释

通过上面的定义我们可以知道,康托展开的作用是找出一个排列在全排列中的位置.
公式也特别容易理解:在它后面且比它小的数都可以放在它前面来一个全排列,这样得到的所有排列一定在此排列的前面.

实现

int fact[10];                                           //fact[i] = i!
fact[0] = 1;
forint i = 1; i < 9; ++i) fact[i] = fact[i-1]*i;int ktint s[], int n) {                                //n个数的排列s[0,n-1]int ans = 0, cnt = 0;                               //返回其在全排列中的位置-1forint i = 0; i < n; ++i) {cnt = 0;                                        //cnt为在i后面出现的小于s[i]的数的个数forint j = i+1; j < n; ++j) ifs[j] < s[i]) ++cnt;ans += cnt*fact[n-i-1];}return ans;
}

康托逆展开

很明显这是一个双射,能正着来肯定也能逆着来.
同样的给出一个位置,我们也应该能还原出这个位置上的排列.
逆着来可以遵循如下流程:

1. 当前数 除以 当前位-1)的阶乘;
2. 得到的商i – 此位答案为未出现的数中第i+1大的数它前面有i个未出现的数),将此数标记表示已出现;
3. 得到的余数r – 赋值给当前数, 继续执行1.

上述步骤每重复一次就会确定一位.
下面举个例子:
求从1到5的全排列中第96个全排列序号为95)

954!商3⏐↓⏐412345−→−−−余23233!商3⏐↓⏐512345−→−−−余552!商2⏐↓⏐312345−→−−−余111!商1⏐↓⏐212345−→−−−余001!商0⏐↓⏐112345

得到答案为{4, 5, 3, 2, 1}

实现

void unKTint s[], int n, int x) {      //找n位全排列[0,n-1]中的第x个排列，存在s里int j, cnt;bool v[20] = {0};forint i = 0; i < n; ++i) {int t = x/fact[n-i-1];          //要找的数后面有t个比它小的数x %= fact[n-i-1];forj = 0; j < n; ++j) if!v[j]) {ift == 0) break;--t;}                               //找未出现的数里第t+1大的数它前面有t个未出现比它小的数)v[j] = 1; s[i] = j;}
}