The Kth Permutation Sequence: Two Approaches

Solution 1: Enumerate K-1 Times

This approach takes little code and is easy to think of, but runs slow.

Time complexity: O(n!) Space complexity: O(n)

string getPermutation(int n, int k) {
    string a(n, '0');
    for(int i=1;i<=n;++i) a[i-1]+=i;
    if (n == 1 || k == 1) return a;
    for(int i=0;i<k-1;i++) next_permutation(a.begin(), a.end());
    return a;
}

Solution 2: Find the Pattern Between Lexicographic Order and K

Proof: K / (n-1)! gives the selected index. The remainder can be used for the next selection, until all n numbers are chosen.

Example: 1, 2, 3, 4. n = 4 When the first digit is 1, there are (n-1)! permutation ways. When the first digit is 2, there are also (n-1)! permutation ways. So the quotient becomes the index of [1, 2, 3, 4], and the remainder shows the position in the next lexicographic sequence after fixing this digit. Both recursive and iterative approaches work.

Time complexity: O(n) Space complexity: O(n)

string getPermutation(int n, int k) {
    string a(n, '0');
    int i;
    for(i=1;i<=n;++i) a[i-1]+=i;
    if (n == 1 || k == 1) return a;

	// Factorial memoization array
    vector<int> v(n, 1);
    for(i=n-3;i>=0;--i) v[i] = v[i+1]*(n-1-i);

    k--;
    string res(n, '0');
    for(i=0;i<n;++i) {
        int select = k/v[i];
        k %= v[i];
        res[i] = a[select];
		// Remove selected character from candidates
        a.erase(select, 1);
    }
    return res;
}

Takeaways

1. Finding the pattern between k and lexicographic permutation order, plus building a factorial table, greatly reduces computation.
2. STL’s erase is an O(n) operation.

#combinatorics