全排列问题与康托编码
全排列问题与康托编码
leetocde的permutation-sequence问题 使用康托编码可以在O(n)是时间内求解。
题目采用康托编码的思路。其实就是康托展开的逆过程。康托展开用来求某个全排列数是第几小的数，也就是当这些数按顺序排时第几个数。
康托展开
过程如下：比如求321 是 第几小的，可以这样来想：小于3的数有1和2 两个，首位确定之后后面两位有2！中情况，所以共有2*2！=4种。
小于2的数只有一个1，所以有11！=1种情况，最后一位是1，没有比一小的数，所以是00！=0
综上：小于321的数有4+1=5个，所以321是第六小的数。
反例与进一步思考
但是康托展开没有这么简单，其实是挺复杂的。以n=4的情况为例子，我们已经知道3412是第17个，也就是说有16个比它小的数字。 首位确定后，有23！=12种，这个是符合的 但是第二位的话是4，此时是先考虑小于4的情况，有1、2、3，然后再排除掉3，所以是22!=4； 第三位的话是1，此时不存在比它小的数字，所以直接排除 最后一位是2，但是枚举发现1已经计算过了，所以也排除。 最终结果是12+4=16，结果正确。虽然思路大体上是一样的，但是原文是没有筛查这个过程的，其实还是有点麻烦的，可能需要开一个集合或者专门的数据结构来进行判断。
康托编码
康托展开的逆过程就是已知这个数是第k个数，求这个数是多少，当然是知道n的值的。
第k个数就是有k-1个数比这个数小。
所以就是 k-1=an*(n-1)!+an-1*(n-2)!+….+a1*0!;
再举一个例子：
如何找出第16个（按字典序的）{1,2,3,4,5}的全排列？
首先用16-1得到15
用15去除4! 得到0余15
用15去除3! 得到2余3
用3去除2! 得到1余1
用1去除1! 得到1余0
有0个数比它小的数是1，所以第一位是1
有2个数比它小的数是3，但1已经在之前出现过了所以是4
有1个数比它小的数是2，但1已经在之前出现过了所以是3
有1个数比它小的数是2，但1,3,4都出现过了所以是5
最后一个数只能是2
代码如下。写的真的挺好，我第一眼还没想明白
class Solution {
public:
//全排列元素数量为n，返回第k个排列
string getPermutation(int n, int k) {
string s(n,'0');//初始是n个零
string result;
for(int i=0;i<n;i++)
{
s[i]+=i+1;//生成默认序列,1->n
}
return kth_permutation(s,k);
}
private:
int factorial(int n)//返回阶乘。其实我觉得这个阶乘可以带个缓存，不过不带也可以了
{
int result=1;
for(int i=1;i<=n;i++)
{
result*=i;
}
return result;
}
string kth_permutation(string &s,int k)
{
const int n=s.size();
string result;
int base=factorial(n-1);
--k;//转换第k个序列为有k-1个小的序列比原序列小
for(int i=n-1;i>0;k=k%base,base/=i,--i)
{
auto a =s.begin()+k/base;//我刚刚才意识到s本质上是剩余数字。使用迭代器来做的移动，绝了。
result.push_back(*a);
s.erase(a);//删掉剩余数字
}
result.push_back(s[0]);
return result;
}
};