关于
联系
Oi大佬们
keyboard_arrow_down
本站已运行
载入天数...载入时分秒...
Woshiluo's Notebook
Woshiluo
2018年1月7日
Caioj 1220:康托展开和康托展开的逆运算

宽搜剪枝法!智障展开康托展开

何为康托展开


对于一个有n个不同元素的集合{1,2,3,4,…,n}的从小到大排序(从大到小 同理)的全排列

显然它有n!项。如n=4,那么就有4!=4×3×2×1=24项。

那么问题来了,如果我们已经知道他的顺序了,要求他是中剪第几个该怎么办呢?
比如下面这道题:

求4132是第几个排列?

我们来看,它是从小到大排的序,我们就要考虑,比它小的有几个

先看千位:4
小于 4 的数有: 3 2 1
那么总共有几种呢? 这时问题就变成了

有三个数进行全排列,总共有多少种可能?

3!=321=6

又因为他有三个比它小的数
所以有 3*3!=18种排列

那么以此类推,我们再往下一位看,此时问题变成这样

求132是第几个排列?

先看最高位-1 小于 1 的数有0个

所以有0种排列

问题继续转化,变成

求32是第几个排列?

小于最高位: 3 并且没有出现过的数有: 2

将一个数进行全排列,总共有多少种排列?

1!=1

综上所述,小于4132的排序有 18+1=19 种 那么,4132就是第20种

上面这些就是康托展开

逆运算?


看看这个问题

1~4从小到大全排列中,找出第20个排列? 和上面的刚好反过来了,怎么办呢?

还是一样,比它小的有19个
我们先考虑一下它的千位

我们想一下,如果千位上的数是固定的,有多少种排列?
3!=321=6 种

所以每过六种排序,千位上的数就会加1

19/6=3…1

所以千位上应该1-4中从小到大第四个没有出现过的数: 4

继续转化问题,上面那个除法算出来还余 2 呢!

1-3从小到大的全排列中,求第2个排列?

1/2!=0…1

所以千位上应该1-4中从小到大第一个没有出现过的数: 1

带着1继续转化问题:

2-3从小到大的全排列中,求第1个排列?

1/1!=1

所以千位上应该1-4中从小到大第二个没有出现过的数: 3

那么最后一位就是剩下唯一没有用过的数字: 2

也就是说,这个排列是4 1 3 2

是不是和上面那个吻合呢?

自己试几个吧!

代码


康托展开

long long zys(){
    long long ans=0;// ans 储存和
    memset(x,false,sizeof(x));// 清空判重数组
    for(long long i=1;i<=n-1;i++){
        long long tcnt=0;
        for(long long j=1;j<a[i];j++) if(x[j]==false) tcnt++;// 寻找有几个比当前数小的
        ans=ans+tcnt*p[n-i];// 结果相加
        x[a[i]]=true;
    }
    ans++;// 加上自己
    return ans;// 返回
}

康托展开逆运算

void nys(long long cnt){
    cnt--;// cnt 第cnt个排列
    memset(x,true,sizeof(x));
    for(long long i=1;i<=n;i++){
        long long tcnt=cnt/p[n-i];
        cnt-=tcnt*p[n-i];// 将cnt的值变成余数
        long long j;
        for(j=1;j<=n;j++){
            if(x[j]==true){
                if(tcnt==0) break;
                tcnt--;
            }    
        }
        x[j]=false;
        a[i]=j;
    }
  // 输出
    for(long long i=1;i<n;i++) printf("%lld ",a[i]);
    printf("%lld\n",a[n]);
}