5

数学笔记：康托展开

 3 years ago
source link: https://ksmeow.moe/cantor_expansion/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client

康托展开（Cantor Expansion）

概述及流程

利用康托展开，我们可以求出一个排列在全排列中的排名，一个排列的康托展开是它的前述排名-1。因此，康托展开是一个排列到自然数的双射，具有双向的唯一映射关系。
我们令康托展开的结果为X，对于排列Ai，有展开式
X=a1(n−1)!+a2(n−2)!+⋯+an⋅0!
展开式中的ai代表，在A1到Ai中没出现过的，不大于Ai的[1,n]中的数的数量。下面我们用一个例子来说明。
排列1 2 4 3 5的康托展开是X=2，展开式为
X=0⋅4!+0⋅3!+1⋅2!+0⋅1!+0⋅0!
A1=1之前没出现过的不大于1的数不存在，因此a1=0，而A3=4之前有1个没出现过的数3，因此a3=1。

// Code by KSkun, 2018/7
LL res = 0;
for(int i = 1; i <= n; i++) {
    int cnt = 0;
    for(int j = 1; j <= i; j++) {
        if(a[j] <= a[i]) cnt++;
    }
    res += mul[n - i] * (a[i] - cnt);
}

注：代码中mul[i]=i!。

康托展开的逆运算

概述及流程

通过逆运算，我们可以把一个康托展开后的值还原成对应的排列。我们只需要逆着做上述过程就好。例如，我们知道了大小为5的排列的值X=4，现在将其展开。
我们先确定第一位，求出a1=X4!=0，因此要从前面没出现过的数中找到第1个数填入，即A1=1。然后将X变为Xmod4!=4。
类似地，A2=2。
到第三位的时候，a3=X2!=2，意义是从前面没出现过的数中找到第3个，即A3=5。
接着做完整个流程，得到了排列1 2 5 3 4。

// Code by KSkun, 2018/7
memset(vis, 0, sizeof(vis));
for(int i = 1; i <= n; i++) {
    LL num = res / mul[n - i];
    res %= mul[n - i];
    for(int j = 1; j <= n; j++) {
        if(!vis[j]) {
            if(!num) {
                a[i] = j; vis[j] = true; break;
            }
            num--;
        }
    }
}

例题：[USACO11FEB]牛线Cow Line

查询一个排列在全排列中的排名，及给排名求排列。

直接实现康托展开和逆康托展开即可。

// Code by KSkun, 2018/7
#include <cstdio>
#include <cctype>
#include <cstring>

#include <algorithm>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2)
        ? EOF : *p1++;
}

inline LL readint() {
    register LL res = 0, neg = 1; register char c = fgc();
    for(; !isdigit(c); c = fgc()) if(c == '-') neg = -1;
    for(; isdigit(c); c = fgc()) res = (res << 1) + (res << 3) + c - '0';
    return res * neg;
}

inline char readop() {
    char c;
    while(!isupper(c = fgc())) {}
    return c;
}

const int MAXN = 25;

int n, k, a[MAXN];
bool vis[MAXN];
LL mul[MAXN];

int main() {
    mul[0] = mul[1] = 1;
    for(int i = 2; i <= 20; i++) {
        mul[i] = mul[i - 1] * i;
    }
    n = readint(); k = readint();
    while(k--) {
        char op = readop();
        if(op == 'P') {
            memset(vis, 0, sizeof(vis));
            LL res = readint() - 1;
            for(int i = 1; i <= n; i++) {
                LL num = res / mul[n - i];
                res %= mul[n - i];
                for(int j = 1; j <= n; j++) {
                    if(!vis[j]) {
                        if(!num) {
                            printf("%d ", j); vis[j] = true; break;
                        }
                        num--;
                    }
                }
            }
            puts("");
        } else {
            LL res = 0;
            for(int i = 1; i <= n; i++) {
                a[i] = readint();
            }
            for(int i = 1; i <= n; i++) {
                int cnt = 0;
                for(int j = 1; j <= i; j++) {
                    if(a[j] <= a[i]) cnt++;
                }
                res += mul[n - i] * (a[i] - cnt);
            }
            printf("%lld\n", res + 1);
        }
    }
    return 0;
}

report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK