全排列问题与康托编码

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;
    }
};
0%