康拓展开主要用于解决字典序排列问题。
问题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;
}
