60.Permutation Sequence¶

60.Permutation Sequence¶

Tags: Math Backtracking Medium

Links: https://leetcode.com/problems/permutation-sequence/

The set [1,2,3,...,*n*] contains a total of n! unique permutations.

By listing and labeling all of the permutations in order, we get the following sequence for n = 3:

"123"
"132"
"213"
"231"
"312"
"321"

Given n and k, return the *k*th permutation sequence.

Note:

Given n will be between 1 and 9 inclusive.
Given k will be between 1 and n! inclusive.

Example 1:

Input: n = 3, k = 3
Output: "213"

Example 2:

Input: n = 4, k = 9
Output: "2314"

Answer:

class Solution {
public:
    string getPermutation(int n, int k) {
        string result;
        vector<int> v;
        int count = 1;

        for (int i = 1; i <= n; ++i)
            v.push_back(i); 

        while(count != k && next_permutation(v.begin(), v.end()))
            ++count;

        for (size_t i = 0; i < v.size(); ++i){
            result += to_string(v[i]);    
        }

        return result;
    }
};

解析：

思路和next_permutation题目较为类似，数组采用vector存储，依次压入，然后调用k-1次next_permutation算法，利用to_string()转int类型为string。但是此种算法耗时较长， $O(k\times n)$ 。leetcode运行的结果是：

Runtime: 324 ms, faster than 14.34% of C++ online submissions for Permutation Sequence.
Memory Usage: 8.4 MB, less than 63.16% of C++ online submissions for Permutation Sequence.

方法二：

class Solution {
public:
    string getPermutation(int n, int k) {
        string s;
        string result;

        for (int i = 0; i < n; ++i)
            s += to_string(i + 1);

        return kth_permutation(s, k);
    }

private:
    int factorial(int n)
    {
        int result = 1;

        for(int i = 1; i <= n; ++i)
            result *= i;

        return result;
    }

    template <typename T>
    T kth_permutation(const T & s, int k)
    {
        const int n = s.size();
        T seq(s);
        T result;

        int base = factorial(n - 1);
        --k;

        for (int i = n - 1; i > 0; k %= base, base /= i, --i){
            auto a = next(seq.begin(), k / base);
            result.push_back(*a);
            seq.erase(a);
        }
        result.push_back(seq[0]);

        return result;
    }
};

思路是康托编码与解码。

编码过程：

(1,2,3,... n)的排列总共有n!种，将它们从小到大排序，怎样知道其中一种排列是有序序列中的第几个？比如321是第6大的数，1324是第3大的数。

以321为例，从最高位往最低位分析，比最高位3小的有两个数字是2，1，分别作为最高位肯定小于321，所以有 $2\times 2!$ 种排列，第二位2来看，只有1比它小，所以有 $1\times 1!$ 种。

再举个例子：1324是{1,2,3,4}排列数中第几个大的数：第一位是1小于1的数没有，是0个， $0\times3!$ ，第二位是3小于3的数有1和2，但1已经在第一位了，所以只有一个数2， $1\times2!$ 。第三位是2小于2的数是1，但1在第一位，所以有0个数， $0\times1!$ ，所以比1324小的排列有 $0\times 3!+1\times 2!+0\times 1!=2$ 个，1324是第三个大数。

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

int factorial(int n)
{
    int result = 1;

    for(int i = 1; i <= n; ++i)
        result *= i;

    return result;
}

int Cantor_encode(const string & s)
{
    int result = 1;
    int n = s.size();

    for(int i = 0; i < n; ++i){
        int coefficient = 0;
        for (int j = i + 1; j < n; ++j){
            if (s[j] < s[i])
                ++coefficient;
        }
        result +=  coefficient * factorial(n - 1 - i); 
    }

    return result;
}

int main()
{
   int example1 = Cantor_encode(string("321"));
   int example2 = Cantor_encode(string("1324"));

   cout << example1 << endl;
   cout << example2 << endl;

   return 0;
}

# run result
6
3

解码过程：

如何找出第16个（按字典序的）{1,2,3,4,5}的全排列？（仅仅是一个例子）

我们用num代表目前这个数字在全排列中的序号，根据编码过程我们可得以下公式： $$ num = 1 + a_0 (n - 1)!+a_1(n-2)! + \cdots + a_{n-1}\times 1! $$ 显然可得： $$ \frac{num - 1}{(n-1)!} = a_0 + \frac{a_1(n-2)! +\dots a_{n-1}\times 1!}{(n-1)!} \ (num - 1) / (n-1)! = a_0 \ (num - 1) \% (n - 1)! = a_1(n-2)! +\dots a_{n-1}\times 1! $$

首先用16-1得到15
用15去除4! 得到0余15
用15去除3! 得到2余3
用3去除2! 得到1余1
用1去除1! 得到1余0
最高位有0个数比它小，所以最高位是1
其次是有2个数比它小，1已经出现过，所以这一位只能是4
这一位有1个数比它小，1已经出现过，所以这一位只能是3
这一位有1个数比它小，但1，3，4都出现过了，所以这一位是5
那么最后一位只能是2，所以结果是14352

程序就是leetcode所描述的问题。这种方法运行效率很高 $O(n)$ 。

Runtime: 0 ms, faster than 100.00% of C++ online submissions for Permutation Sequence.
Memory Usage: 8.4 MB, less than 31.58% of C++ online submissions for Permutation Sequence.