Permutation Sequence

LeetCode #60

Description:

Example:

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 (ie, for n = 3):

"123"
"132"
"213"
"231"
"312"
"321"
Given n and k, return the kth permutation sequence.

Note: Given n will be between 1 and 9 inclusive.

Idea:

利用康托编码的思路，假设有 n 个不重复的元素，第 k 个排列是 a_1 ,a_2 ,a_3 ,...,a_n ，那么 a_1 是 哪一个位置呢？ 我们把 a_1 去掉，那么剩下的排列为 a_2 ,a_3 ,...,a_n , 共计 n−1 个元素，n−1 个元素共有 (n−1)! 个排列，于是就可以知道 a_1 = k/(n − 1)!。 同理，a_2 ,a_3 ,...,a_n 的值推导如下： k_2 = k%(n − 1)! a_2 = k_2 /(n − 2)! ··· k_n−1 = k_n−2 %2! a_n−1 = k_n−1 /1! a_n = 0

Code:

class Solution {
public:
    string getPermutation(int n, int k) {
        string sequence(n, '1');
        for(int i=0; i<n; ++i){
            sequence[i] += i;
        }

        string result;

        // only calculate (n-1)!
        int base = factorial(n-1);
        k--; // the kth sequence starts from 0th.

        for(int i=n-1; i>0; --i){
            int ind = k/base;
            auto iter = sequence.begin() + ind;
            result.push_back(*iter);
            sequence.erase(iter);
            k = k%base;
            base = base/i;
        }

        result.push_back(sequence[0]);
        return result;
    }

    int factorial(int n){
        int result=1;
        for(int i=1; i<=n; ++i){
            result *= i;
        }
        return result;
    }
};