leetcode筆記：Permutation Sequence

一.題目描述

題目的意思是，假設有{1,2,3,4,…,n}，對其中的元素進行排列，總共有n!種組合，將它們從小到大排序，問其中第k個組合的形式是怎樣的？<喎?/kf/ware/vc/" target="_blank" class="keylink">vcD4NCjxwPjxzdHJvbmc+tv4uzOLEv7fWzvY8L3N0cm9uZz48L3A+DQo8cD48c3Ryb25nPre9t6jSuzwvc3Ryb25nPqO6v8nS1NK7uPbSu7j2tcSwtLTO0PKxqcGmx/O94qGjvt/M5cq1z9a/ybLO1dXM4sS/o7pOZXh0IFBlcm11dGF0aW9uoaPV4sDvsqLDu9PQyrXP1qOs1vfSqtHQvr+1xMrHt723qLb+tcRDYW50b3IgZXhwYW5zaW9uy+O3qKGjPC9wPg0KPHA+PHN0cm9uZz63vbeotv48L3N0cm9uZz6jusr90ae94reoo7pDYW50b3IgZXhwYW5zaW9uPC9wPg0KPHA+Q2FudG9yIGV4cGFuc2lvbsvjt6i1xMu8z+vKx6Os1No8Y29kZT5uITwvY29kZT649sXFwdDW0KOstdrSu867tcTUqsvY19zKxzxjb2RlPihuLTEpITwvY29kZT7Su9fps/bP1rXEo6zSsr7Ny7XI57n7PGNvZGU+cCA9IGsgLyAobi0xKSE8L2NvZGU+o6zEx8O0xcXB0LXE1+6/qsq80ru49tSqy9jSu7aoysc8Y29kZT5udW1zW3BdPC9jb2RlPqGj0tTPwrmryr24+LP2wcvIq8XFwdC1vdK7uPbX1Mi7yv21xNK70rvLq8nko7o8L3A+DQo8cHJlIGNsYXNzPQ=="brush:java;"> 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 
#include 
#include 
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的取值超過可能的組合數量時：