LeetCode Permutation Sequence: Math Approach Rather Than DFS

Overview

To solve LeetCode Permutation Sequence, math could be adopted to identify the correct number in the corresponding position rather than do DFS simulation.

LeetCode Permutation Sequence

The set [1,2,3,…,<i>n</i>] 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):

  1. "123"
  2. "132"
  3. "213"
  4. "231"
  5. "312"
  6. "321"

Given n and k, return the kth permutation sequence.

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

Solution Analysis: Math Approach Rather Than DFS

(1) DFS and enumerate all the sequences by the increasing order, when enumerate the k-th sequence, return it. This would be TLE for large test case

(2) Actually there is “O(n)” solution. From pure mathematical view, for example we want to find k-th sequence of length n, basically let a[1]…a[n] denote the k-th sequence, think about this: except a[1] there are totally (n-1)! different permutations for a[2]…a[n], then a[1] = k / (n-1)! and we need to find k % (n-1)! -th element is the a[2]…[an] sequence, this is recursively the same problem. Just be careful when dealing with some border cases like k is exactly (n-1)! or 3 * (n-1)! sort of these cases. The following code is accepted by LeetCode OJ to pass this Permutation Sequence problem:

string getPermutation(int n, int k) {
    string sol;
    vector<char> nums;
    int per[10];  
    per[0] = per[1] = 1; 
    for (int i = 1; i <= n; ++i) {
        per[i] = i * per[i-1];
        nums.push_back('0' + i);
    }
    int v = 0;
    for (int i = n; i >= 1; --i) {
        v = (k - 1) / per[i - 1];  
        sol.push_back(nums[v]);
        nums.erase(nums.begin() + v); 
        k = (k - 1) % per[i-1] + 1; 
    }
    return sol;
}

And not that the real time complexity is O(N^2) because erase operation takes O(N) time, I say this is a “O(N)” approach in a sense of that it just linear scan the permutation to generate the final result.

Summary

To solve LeetCode Permutation Sequence, math could be adopted to identify the correct number in the corresponding position rather than do DFS simulation.

Written on June 15, 2013