2016 September 08

康拓展开

康拓展开主要用于解决字典序排列问题。

问题1：集合{1,2,3,4,5,6,7,8,9}构成的全排列有9!个，问357412968在所有全排列中字典序排第几小？

分析：先计算比该排列小的排列有多少个。  
当前集合：{1,2,3,4,5,6,7,8,9}，第1位是3，比3小的数有2个，3后面有8个位置，因此有2 x 8!种排列；  
当前集合：{1,2,4,5,6,7,8,9}，  第2位是5，比5小的数有3个，5后面有7个位置，因此有3 x 7!种排列；  
当前集合：{1,2,4,6,7,8,9}，    第3位是7，比7小的数有4个，7后面有6个位置，因此有4 x 6!种排列；  
当前集合：{1,2,4,6,8,9}，      第4位是4，比4小的数有2个，4后面有5个位置，因此有2 x 5!种排列；  
当前集合：{1,2,6,8,9}，        第5位是1，比1小的数有0个，1后面有4个位置，因此有0 x 4!种排列；  
当前集合：{2,6,8,9}，          第6位是2，比2小的数有0个，2后面有3个位置，因此有0 x 3!种排列；  
当前集合：{6,8,9}，            第7位是9，比9小的数有2个，9后面有2个位置，因此有2 x 2!种排列；  
当前集合：{6,8}，              第8位是6，比6小的数有0个，6后面有1个位置，因此有0 x 1!种排列；  
当前集合：{8}，                第9位是8，比8小的数有0个，8后面有0个位置，因此有0 x 0!种排列；  
综上，总共有2x8!+3x7!+4x6!+2x5!+0x4!+0x3!+2x2!+0x1!+0x0!=98884个排列比所给排列小，因此该排列为第98885小。

问题2：集合{1,2,3,4,5,6,7,8,9}构成的全排列有9!个，问所有全排列中字典序排在第98885小的排列是什么？

分析：有98885-1=98884个全排列比所求排列小。  
当前集合：{1,2,3,4,5,6,7,8,9}，98884 / 8! = 2 余 18244，集合中有2个比它小的数是3，所以第1位是3；  
当前集合：{1,2,4,5,6,7,8,9}，  18244 / 7! = 3 余 3124， 集合中有3个比它小的数是5，所以第2位是5；  
当前集合：{1,2,4,6,7,8,9}，     3124 / 6! = 4 余 244，  集合中有4个比它小的数是7，所以第3位是7；  
当前集合：{1,2,4,6,8,9}，        244 / 5! = 2 余 4，    集合中有2个比它小的数是4，所以第4位是4；  
当前集合：{1,2,6,8,9}，            4 / 4! = 0 余 4，    集合中有0个比它小的数是1，所以第5位是1；  
当前集合：{2,6,8,9}，              4 / 3! = 0 余 4，    集合中有0个比它小的数是2，所以第6位是2；  
当前集合：{6,8,9}，                4 / 2! = 2 余 0，    集合中有2个比它小的数是9，所以第7位是9；  
当前集合：{6,8}，                  0 / 1! = 0 余 0，    集合中有0个比它小的数是6，所以第8位是6；  
当前集合：{8}，                    0 / 0! = 0 余 0，    集合中有0个比它小的数是8，所以第9位是8；  
综上，357412968就是要求的排列。

例题

给定一个1~n的排列，问该排列对应的排名。假定字典序最小的排列对应的排名为1。

#include <iostream>
#include <vector>
using namespace std;
const int N = 10;
int fac[N];
int cantor(const vector<int> &a)
{
    int k = 1;
    int n = a.size();
    for (int i = 0; i < n; i++)
    {
        int rev = 0;
        for (int j = i+1; j < n; j++)
        {
            if (a[i] > a[j])
            {
                rev += 1;
            }
        }
        k += rev * fac[n-i-1];
    }
    return k;
}
int main()
{
    fac[0] = 1;
    for (int i = 1; i < N; i++)
    {
        fac[i] = i * fac[i-1];
    }

    int n, x;
    while (cin >> n)
    {
        vector<int> a;
        for (int i = 0; i < n; i++)
        {
            cin >> x;
            a.emplace_back(x);
        }
        cout << cantor(a) << endl;
    }
    return 0;
}

给定n和排名k，求对应的1~n排列。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 10;
int fac[N];
void decantor(int n, int k)
{
    vector<int> ans;
    vector<int> A;
    for (int i = 1; i <= n; i++)
    {
        A.emplace_back(i);
    }
    k -= 1;
    for (int i = 0; i < n; i++)
    {
        int t = k / fac[n-i-1];
        k %= fac[n-i-1];
        sort(A.begin(), A.end());
        ans.emplace_back(A[t]);
        A.erase(A.begin()+t);
    }
    for (auto i : ans)
    {
        cout << i << " ";
    }
    cout << endl;
}
int main()
{
    fac[0] = 1;
    for (int i = 1; i < N; i++)
    {
        fac[i] = i*fac[i-1];
    }

    int n, k;
    while (cin >> n >> k)
    {
        decantor(n, k);
    }
    return 0;
}
Table of Contents