康托展开 X=a[n](n-1)!+a[n-1](n-2)!+...+a[i](i-1)!+...+a[1]0! 其中,a[i]为整数,并且X=a[n](n-1)!+a[n-1](n-2)!+...+a[i]*(i-1)!+...+a[1]*0!。这就是康托展开。康托展开可用代码实现。

——百度百科

这个东西,我们高三的时候称作OhYee第一定理(还有第二第三)。当时做排列组合做到疯的时候推出来的。然而我们数学老师觉得没什么琴里用→_→

对于八数码问题,在储存时有一个问题,就是八数码共有9!=362800种可能,但是如果用9维数组,包含了99=387420489项,显然造成了极大地浪费。

当然,我们可以采用哈希表来进行映射,而哈希函数便可以使用康托展开(OhYee第一定理)

当年我可是在有OhYee第一定理的情况下做过八数码的,可惜当时竟然没有想到用OhYee第一定理。。。

嗯嗯,我们就不管是康托展开,还是康托逆展开了,反正都是OhYee定理的内容23333333333


含义

对于{1,2,3,4}其排列有:1234,1243,1324,1342,1423,1432,2134,2143,2314,2341,2413,2431,3124,3142,3214,3241,3412,3421,4123,4132,4213,4231,4312,4321共24种。

这样我们就可以按照从小到大的顺序,给他们编上号,就有了一个映射关系


1 2 3 4 5 6 7 8 9 10 11 12
1234 1243 1324 1342 1423 1432 2134 2143 2314 2341 2413 2431
13 14 15 16 17 18 19 20 21 22 23 24
3124 3142 3214 3241 3412 3421 4123 4132 4213 4231 4312 4321

这样将序号和数字的映射就是康托(逆)展开


原理

由上面{1,2,3,4}的例子很容易发现,从小到大排列,有着一定的规律。

以每个数开头的,分别占据了总数(4!)的1/4,即3!。

第一个以1开头的在0×3!+1=1

第一个以2开头的在1×3!+1=7

……

也就是说N个数全排列,第一个数是x的数出现在(x-1)×(N-1)!+1处。

第一个数确定后,我们再看第二个数。假如第一个数是2,那么还有{1,3,4}三个数。

令1=1,2=3,3=4,我们便可看成{1,2,3}三个数的排列

假如是那么第一个2便在1×2!+1=3

再映射回去,也就是第二个是3的在第3个,对照上表看,在第一个是2的数中第二个是3的第一个数就是第3个

就这样,不断类比下去,就可以得到一个数在其排列中的位置。这就是OhYee第一定理

ps:最后的+1只需要加一次


例子

假如我们想要计算在{1,2,3,4}的全排列中,2413的位置

首先有对2,比2小的有1,共1个。1×3!=6

此时剩下1,3,4。

然后对4,比4小的有1,3,共2个。2×2!=4

此时剩下1,3。

然后对1,比1小的有0个。0×1!=0

此时剩下3,比3小的有0个。0×0!=0

所以,2413的位置是6+4+0+0+1=11


逆着来一遍

排列中,第11个是什么呢~

首先划分区间3!=6,也就是6个一组(以相同的数字开头)

这样11-6=5<=6 在第2区间。第一个数是2

再往下划分区间2!=2

5-2=3  3-2=1<=2在第3区间。第二个数是4

再往下划分1!=1

1<=1在第一区间。第三个数是1

再往下划分0!=1

1<=1在第一区间。第四个数是3

所以,第11个数是2413

根据上面的分析,我们需要不断插入删除数字,需要用链表来记录还存在的数

用指针弄一个链表(输出了中间运算过程)

链表

class linked_list{
private:
    struct link{
        int num;
        link *next;
    };
    link *head;

public:
    linked_list(){
        head=NULL;
    }
    void Add(int n){
        link *it;
        if(head==NULL){
            head=new link;
            it=head;
        }else{
            it=head;
            while((it->next)!=NULL){
                it=it->next;
            }
            it->next=new link;
            it=it->next;
        }
        it->num=n;
        it->next=NULL;
        cout<<"add "<<n<<"  ("<<it<<")"<<endl;
    }
    void Del(int n){
        link *it=head;
        if(it->num==n){
            head=it->next;
            delete(it);
            cout<<"delete "<<n<<"   ("<<it<<")\n";
            return;
        }
        while(it->next->num!=n){
            it= it->next;
            if(it->next==NULL)return;
        }
        link *temp=it->next;
        it->next=it->next->next;
        delete(temp);
        cout<<"delete "<<n<<"   ("<<temp<<")\n";
    }
    int get(int n){
        link *it=head;
        int cnt=0;
        cout<<"begin ";
        while(it->num!=n){
            cout<<"---->"<<it<<"("<< it->num <<") ";
            it=it->next;
            cnt++;
        }
        cout<<endl;
        return cnt;
    }
    int get2(int n){
        link *it=head;
        cout<<"begin ";
        while(n>1){
            cout<<"---->"<<it<<"("<< it->num <<") ";
            it=it->next;
            n--;
        }
        cout<<"---->"<<it<<"("<< it->num <<") "<<endl;
        return it->num;
    }
};

其中Add()是向链表最后插入,Del()是删除存储制定数据的节点,get()是获取指定数据前面的节点数,get2()是获取指定节点存储的数

代码

int factorial[]={1,1,2,6,24,120,720,5040,40320};//n!
int KT(int N,int x){
    int ans=1;
    linked_list L;
    stack<int> S;
    while(x){
        S.push(x%10);
        x/=10;
    }
    REP(N){
        L.Add(o+1);
    }
    REP(N){
        int a=L.get(S.top());
        L.Del(S.top());
        S.pop();
        ans+=a*factorial[N-o-1];
    }
    return ans;
}
int KTN(int N,int n){
    int ans=0;
    linked_list L;
    REP(N){
        L.Add(o+1);
    }
    REP(N){
        ans*=10;
        int t=1;
        while(n>factorial[N-o-1]){
            n-=factorial[N-o-1];
            t++;
        }
        int temp=L.get2(t);
        ans+=temp;
        L.Del(temp);
    }
    return ans;
}