leetcode笔记：Permutation Sequence

一.题目描述

题目的意思是，假设有{1,2,3,4,…,n}，对其中的元素进行排列，总共有n!种组合，将它们从小到大排序，问其中第k个组合的形式是怎样的？

二.题目分析

方法一：可以一个一个的按次序暴力求解。具体实现可参照题目：Next Permutation。这里并没有实现，主要研究的是方法二的Cantor expansion算法。

方法二：数学解法：Cantor expansion

Cantor expansion算法的思想是，在n!个排列中，第一位的元素总是(n-1)!一组出现的，也就说如果p = k / (n-1)!，那么排列的最开始一个元素一定是nums[p]。以下公式给出了全排列到一个自然数的一一双射：

X=an*(n-1)!+an-1*(n-2)!+...+ai*(i-1)!+...+a2*1!+a1*0!

举个例子：

问1324是{1,2,3,4}排列数中第几个组合：

第一位是1，小于1的数没有，是0个，0*3!，第二位是3，小于3的数有1和2，但1已经存在于第一位了，所以只有一个数2，1*2! 。第三位是2小于2的数是1，但1在第一位，所以有0个数，0*1!，所以比1324小的排列有0*3!+1*2!+0*1!=2个，1324是第3个组合。

以上是Cantor编码的过程，即把一个全排列映射1324为一个自然数3，而该题目是已知一个自然数k，求其对应的全排列，相对以上步骤来说是一个解码的过程，下面给出一个具体的例子：

如何找出{1,2,3,4,5}的第16个排列？
1. 首先用16-1，得到15；
2. 用15去除4! ，得到0，余15；
3. 用15去除3! ，得到2，余3；
4. 用3去除2! ，得到1，余1；
5. 用1去除1! ，得到1，余0；
6. 有0个数比它小的数是1，所以第一位是1；
7. 有2个数比它小的数是3，但1已经在之前出现过，所以第二位是4；
8. 有1个数比它小的数是2，但1已经在之前出现过了所以第三位是3；
9. 有1个数比它小的数是2，但1,3,4都出现过了所以第四位是5；
10. 根据上述推论，最后一个数只能是2；

所以排列为{1,4,3,5,2}。

按照以上思路，可以开始设计算法。

三.示例代码

#include <iostream>
#include <string>
#include <iterator>
using namespace std;

class Solution
{
public:
    string PermutationSequence(int n, int k)
    {
        int total = CombinedNumber(n - 1);
        if (k > total)
        {
            cout << "The k is larger then the total number of permutation sequence:" << total << endl;
            return "Null!";
        }

        string a(n, ‘0‘);
        for (int i = 0; i < n; ++i)
            a[i] += i + 1;   // sorted

        // Cantor expansion
        string s = a, result;
        k--; // (k - 1) values are less than the target value 

        for (int i = n - 1; i > 0; --i)
        {
            auto ptr = next(s.begin(), k / total);
            result.push_back(*ptr);
            s.erase(ptr);  // delete the already used number
            k %= total;    // update the dividend
            total /= i;    // update the divider
        }
        result.push_back(s[0]);  // The last bit
        return result;
    }

private:
    int CombinedNumber(int n)
    {
        int num = 1;
        for (int i = 1; i < n + 1; ++i)
            num *= i;
        return num;
    }
};

以下是简易的测试代码：

#include "PermutationSequence.h"

int main()
{
    Solution s;

    int n = 6, k = 150;
    string result = s.PermutationSequence(n, k);

    std::cout << "n = " << n << " and the " << k << "th sequence is: " << result << std::endl;

    getchar();

    return 0;
}

一个正确的测试结果，n = 6， k = 16：

当k的取值超过可能的组合数量时：

四.总结

该题应尝试使用Cantor expansion解法来做，数学的魅力是无穷的。

参考资料：http://www.bianceng.cn/Programming/sjjg/201407/43080.htm