Permutation Sequence

• leetcode 60
• Medium
• Company Tags: Twitter
• Tags: Backtracing, Math
• Similar Problems: Next Permutation, Permutations

Description

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.

Previous Thinking

Assuming the k th permutation is a₀,a₁,a₂,...a_n-1, , Then a_i should be k_i / (n - i)! th largest number in range from a_i to a_n-1. k_i = k_i-1 % (n - i).

C++ Solution

It is clear to clarify the thinking.

class Solution {
public:
    string getPermutation(int n, int k) {
        int factorial = 1;
        string s(n,'0');

        for(int i = 1; i <= n; i++){
            factorial *= i;
            s[i - 1] += i; 
        }

        k--;

        for(int i = 0; i < n; i++ ){

            factorial /= (n - i);

            int j = i + k / factorial;
            char c = s[j];

            for( ; j > i ; j--){
                s[j] = s[j - 1];
            }

            k %= factorial;
            s[i] = c;

        }

        return s;
    }
};

Notice k-- is because that the initial permutation has already been the first one.

Java Solution

public class Solution {
    public String getPermutation(int n, int k) {
        int factorial = 1;

        List<Integer> s = new LinkedList<>();

        StringBuilder sb = new StringBuilder();

        for(int i = 1; i <= n; i++){
            factorial *= i;
            s.add(i);
        }

        k--;
        for(int i = 0; i < n; i++){
            factorial /= (n - i);
            int j = i + k / factorial;

            s.add(i, s.remove(j));

            k %= factorial;
            sb.append(s.get(i));
        }

        return sb.toString();
    }
}

• LinkedList rather than ArrayList is to speed the deletion and insertion .
• Java provide a more convenient way to re-order the list.
• StringBuilder is faster than string.