全排列_获取第几个排列_获取是第几个排列__康托展开,逆康托展开

#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

// 适用范围: int: n --> [0, 15]     long long: n--> [0, 21]
class Cantor_Expansion{
public:
    // 阶乘数组  
    const int fac[16] = {1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800, 39916800, 479001600, 1932053504, 1278945280, 2004310016}; 
    vector<int> cve, tve;
    int cn;
    
    // 下标从0开始, 返回排列在全排列中的次序.
    // @ arr[]  排列数组
    // @ n     排类长度 
    int Getid(int arr[], int n)    {
        int i, j, cnt, res = 0;    
        for (i=0; i<n; ++i) {
            cnt = 0;
            for (j=i+1; j<n; ++j) 
                if (arr[j] < arr[i]) cnt++;
            res += fac[n-i-1] * cnt;
        } 
        return res;
    }
    
    // 如果要返回排列 必须初始化 
    // @arr[]  初始化数组, 下标[0, n-1]
    // @n      长度 
    void init(int arr[], int n) {
        int i;
        cve.clear();
        for (i=0; i<n; ++i) 
            cve.push_back(arr[i]); 
        sort(cve.begin(), cve.end());
        cn = n;
    }
    
    // 返回排第k的排列  排列时从 0开始的. [0, n!-1] 
    // @arr[] 保存答案的数组  下标从0开始 
    // @id    要获得的排列的名次 
    int GetArr(int arr[], int id) {
        int i, t, cnt = 0;
        tve.assign(cve.begin(), cve.end());
        for (i=cn-1; i>=0; --i) {
            arr[cnt++] = tve[id / fac[i]];
            tve.erase(tve.begin()+(id / fac[i])); 
            id = id % fac[i];
        }
    }
}ct; 

int main()
{ 
    
    // 逆展开 获取排序 
    int i, arr[5];
    int tarr[] = {3, 4, 1, 5, 2};
    ct.init(tarr, 5);
    ct.GetArr(arr, 1);
    for (i=0; i<5; ++i) 
        printf("%d ", arr[i]);
    
    // 顺展开获取id 
    printf("
%d", ct.Getid(tarr, 5));
    
    return 0;
}