康托展开和逆康托展开

转博客：https://blog.csdn.net/wbin233/article/details/72998375

康托展开

 1 static const int FAC[] = {1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880};   // 阶乘
 2 int cantor(int *a, int n)
 3 {
 4     int x = 0;
 5     for (int i = 0; i < n; ++i) {
 6         int smaller = 0;  // 在当前位之后小于其的个数
 7         for (int j = i + 1; j < n; ++j) {
 8             if (a[j] < a[i])
 9                 smaller++;
10         }
11         x += FAC[n - i - 1] * smaller; // 康托展开累加
12     }
13     return x;  // 康托展开值
14 }

逆康托展开

static const int FAC[] = {1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880};   // 阶乘

//康托展开逆运算
void decantor(int x, int n)
{
    vector<int> v;  // 存放当前可选数
    vector<int> a;  // 所求排列组合
    for(int i=1;i<=n;i++)
        v.push_back(i);
    for(int i=m;i>=1;i--)
    {
        int r = x % FAC[i-1];
        int t = x / FAC[i-1];
        x = r;
        sort(v.begin(),v.end());// 从小到大排序 
        a.push_back(v[t]);      // 剩余数里第t+1个数为当前位
        v.erase(v.begin()+t);   // 移除选做当前位的数
    }
}