康拓展开

Dec 3, 2020 算法学习 #全排列 #康拓展开

康拓展开(全排列排名)

思路

康拓展开是求一个全排列是第k小，思路很简单，我们求出比这个排列小的排列的数量，对于a[i]，显然比a[i]小的数都可以放在这个位置，然后后面的位置随便放，方案数就是一个阶乘，当然，因为是全排列，为了避免重复使用数字，所以求的是在i的后面比a[i]小的数的个数。即$rk=b_n(n-1)!+b_{n-1}(n-2)!+…b_10!$，其中$b_i$就是表示在i的后面比a[i]小的数的个数。

朴素做法是O(N^2)，可以用树状数组/线段树来优化计算$b_i$，复杂度为O(NlogN)。

代码

int cantor(vector<int>& perm){
    int n=perm.size();
    int ans=0;
    for(int i=0;i<n;i++){
        int cnt=0;
        for(int j=i+1;j<n;j++){
            if(perm[j]<perm[i]){
                cnt++;
            }
        }
        ans+=cnt*fac[n-1-i];
    }
    return ans+1;
}

逆康拓展开(第k个全排列)

思路

逆康拓展开是指求第k个全排列，是康拓展开的逆过程，我们依次确定每一位，通过除以阶乘计算有多少个数比a[i]小，通过取模得到下一位所对应的排名，同样的，为了避免重复使用数字，我们用一个标记数组来维护还没用过的数字。

朴素做法是O(N^2)，可以用树状数组/线段树/主席树/平衡树来维护未使用的数字，复杂度为O(NlogN)。

代码

vector<int> revCantor(int n,int k){
    vector<int> vis(n+1,0);
    vector<int> ans(n,0);
    int m=k-1;
    for(int i=0;i<n;i++){
        int t=m/fac[n-1-i];
        m-=t*fac[n-1-i];
        for(int j=1;j<=n;j++){
            if(!vis[j]){
                t--;
                if(t==-1){
                    ans[i]=j;
                    vis[j]=1;
                    break;
                }
            }
        }
    }
    return ans;
}

上/下一个全排列

思路

感性理解，肯定是在后面找一个比前面某一个位置大的数，交换，之后后面的部分转为顺序排列，为了使交换后的全排列尽量小，满足"下一个"，这个在前面被交换的数应该尽量靠后，权重更小，然后逆向思维，被交换我们尽量从为了比如1 4 2 5 6 3，

感性理解，下一个全排列肯定是从后往前找到一段满足递增一个，再不断递减到完的后缀，要交换的显然是这个递增的这个，记为x，因为递减就是表示字典序最大了，要交换过去的数就是从后面找到一个刚好大于x的数，记为y，swap(x,y)，然后将后面递减部分逆序成为递增，类似于进位，后面要恢复到字典序最小的递增，为什么要从后往前，因为我们尽量让交换发生在权重更小的后面，满足下一个全排列的要求。

总结起来就是：

next_permutation的思路：从后往前找到一个i满足a[i]<a[i+1]，此时a[i+1…n-1]是递减的，然后再次从后往前找到第一个大于a[i]的数，两数交换，此时a[i+1…n-1]仍然保持递减，将这一部分逆序即可。

prev_permutation的思路：累死next_permutation，符号相反，即从后往前找到一个i满足a[i]>a[i+1]，此时a[i+1…n-1]是递增的，然后再次从后往前找到第一个小于a[i]的数，两数交换，此时a[i+1…n-1]仍然保持递增，将这一部分逆序即可。

代码

STL库函数

prev_permutation(a,a+n);
next_permutation(a,a+n);

vector<int> next_permutation(vector<int>& perm){
    int n=perm.size();
    int idx=-1;
    for(int i=n-1;i>0;i--){
        if(perm[i]>perm[i-1]){
            idx=i-1;
            break;
        }
    }
    if(idx!=-1){
        for(int i=n-1;i>idx;i--){
            if(perm[i]>perm[idx]){
                swap(perm[i],perm[idx]);
                break;
            }
        }
    }
    int l=idx+1;
    int r=n-1;
    while(l<r){
        swap(perm[l++],perm[r--]);
    }
    return perm;
}
vector<int> prev_permutation(vector<int>& perm){
    int n=perm.size();
    int idx=-1;
    for(int i=n-1;i>0;i--){
        if(perm[i]<perm[i-1]){
            idx=i-1;
            break;
        }
    }
    if(idx!=-1){
        for(int i=n-1;i>idx;i--){
            if(perm[i]<perm[idx]){
                swap(perm[i],perm[idx]);
                break;
            }
        }
    }
    int l=idx+1;
    int r=n-1;
    while(l<r){
        swap(perm[l++],perm[r--]);
    }
    return perm;
}