Permutation
排列数¶
n种数字，全部排列有n!种，可以按照字典序排列
求下一个字典序排列¶
从右到左找第一个升序对，然后将较小的前者和后面刚好大于它的那个数交换，接着将后缀升序排列
中介数¶
判断一个排列是第几个排列
7 6 8 3 4 5 1 2
可以这样算，第一位是7，这位如果填1-6，都是字典序更小的排列，一共有6\times 7!个排列
再看第二位，是6，这里填1-5也是更小的排列，一共有5\times 6!个排列
第三位是8，这里填1-7都更小，但因为7和6之前出现过，这里只有5\times 5!个排列，也就是应该看每位上的数字比后面多少个数字大
7 6 8 3 4 5 1 2
6 5 5 2 2 2 0 0
7 6 5 4 3 2 1
所以是第6\times 7! + 5\times 6! + 5\times 5! + 2\times 4! + 2 \times 3 + 2 \times 2!+1=34504
由此生成的中介数可以很方便地和排列进行互相转换
生成第k个排列
要直接生成第k个排列，如果可以直接将k转换成上述的中介数，就可以得到排列
这里可以观察中介数，其实是一个递增进位制数，因为每个位置的值肯定小于位数-1，如上例，每一位的进制其实是
7 6 5 4 3 2 1
5 6 5 2 2 2 0
因为1肯定是0，所以这里直接不考虑这一位
那么，将k从2开始进行模和除运算，可以将其转换成一个递增进位制的中介数
vector<int> convertToMiddle(int n, int k) {
vector<int> middle(10, 0);
k--;
for (int i = 2; i <= n; i++) {
middle[i] = k % i;
k /= i;
}
return middle;
}
将这样的中介数可以转换为排列
string middleToPermu(int n, const vector<int>& v) {
string num = "123456789", res = "";
for (int i = n; i >= 1; i--) {
res += num[v[i]];
num.erase(v[i], 1);
}
return res;
}