Cantor expansion and permutation

17 Jul, 2021

Cantor expansion and inverse of it

Cantor expansion: calculate the rank of a given permutation.

It's inverse: calculate the permutation of a given rank.

Obviously, the rank(from 0) equals the count of permutations which is smaller than it in lexicographic order.

For example, give a permutation a[]=24315, if another permutation is 24xxx, it means the prefix of both are the same, so if we set a number that is smaller than 3 in the third position, then this permutation must be smaller than a(no matter what are the suffix numbers).

So for every number(or prefix) of the given permutation, we can do this and easily get a formulation like $rk=b_n(n-1)!+b_{n-1}(n-2)!+...b_10!$, $b_i$ means the count of number which is smaller than a[i] and locate right of a[i].

The time complexity is O(N^2) and can be optimized to O(NlogN) using a segment tree or binary index tree.

code:

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;
}

For the inverse, we divide by the factorial to determine what number should be set in this index, for every index.

code:

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;
}

Last/Next permutation

To get the next permutation, it needs to satisfy the following:

Switch a bigger number on the right side and a smaller number on the left side(relative).
Let the smaller number be as right as it can.
Let the bigger number be as close to the smaller one as it can.

So the detailed method is following:

Lookup a number $x$ from right to left which is bigger than the next one and the suffix number from the next one is in descending order. Why? see (2).
Lookup the smallest number $y$ from the suffix which is bigger than $x$ Why? see (3).
Switch $x$ and $y$ and then sort the suffix in ascending order.

The last permutation is similar and opposite somewhere.

code:

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;
}

#Algorithm #Cantor Expansion #Permutation