Problem of the day for today is k^{th} permutation: *Given numbers n and k, 1 <= k < INT_MAX, return k ^{th} permutation of the set [1,2,…,n]*. For example, given n=3 and k=4, the permutations of [1,2,3] in order are:

- “123”
- “132”
- “213”
- “231”
- “312”
- “321”

k=4^{th} permutation is “231”. To simplify the output, a string concatenation of the numbers is returned.

How should we think about this problem? Some observations:

- The set [1,2,..,n] has n! permutations.
- There are (n-1)! permutations where 1 is in the first place. When we swap 1 and 2, we skip those (n-1)! permutations. More generally, if we swap the first element with x
^{th}element, we skip (x-1)*(n-1)! permutations.

These two observations are enough to solve this problem. If we divide k by (n-1)!, we’ll get the element we need to swap the first element with. That element will be placed in its correct position in the k^{th} permutation and we can recurse on the remaining elements for k % (n-1)!^{th} permutation.

Now there are some challenges in implementation:

- Calculating n! for all n? We only care about those factorials which are less than INT_MAX, which is true only for n <= 12. So we don’t need to worry about large factorials. We can compute them on the fly.
- How to maintain the set of numbers? We need to find the x
^{th}element from the start (suggesting vector) but also maintain the smaller set in sorted order (suggesting set). A valid trade-off is to use vector and pay linear cost for removing element in the middle or shuffling elements around.

Here’s the recursive solution:

int factorial(int n) { | |

if (n > 12) return INT_MAX; | |

int f = 1; | |

for (int i = 2; i <= n; i++) | |

f *= i; | |

return f; | |

} | |

void getPermutationHelper(vector<int>& num, int k, stringstream& ss) { | |

if (num.size() == 0) return; | |

int f = factorial(num.size() - 1); | |

int incr = k / f; | |

ss << to_string(num[incr]); | |

num.erase(num.begin() + incr); | |

getPermutationHelper(num, k % f, ss); | |

} | |

string getPermutation(int n, int k) { | |

k--; // 0-based indexing | |

if (k >= factorial(n)) return ""; // error | |

vector<int> num(n); | |

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

num[i] = i+1; | |

stringstream ss; | |

getPermutationHelper(num, k, ss); | |

return ss.str(); | |

} |

Tidbits:

- Concatenating n strings using string concatenation would be O(cn
^{2}) operation, where c is the max component string size. Using stringstream instead reduced it to O(cn). - Passing stringstream as an argument to the recursive function made it tail recursive i.e., more space efficient if the compiler implements it properly (we use a single stack frame instead of n frames).

It’s equally easy to implement it iteratively:

int factorial(int n) { | |

if (n > 12) return INT_MAX; | |

int f = 1; | |

for (int i = 2; i <= n; i++) | |

f *= i; | |

return f; | |

} | |

string getPermutation(int n, int k) { | |

k--; // 0-based indexing | |

if (k >= factorial(n)) return ""; // error | |

vector<int> num(n); | |

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

num[i] = i+1; | |

stringstream perm; | |

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

int fact = factorial(n-i-1); | |

int incr = k / fact; | |

int t = num[i+incr]; | |

for (int j = i+incr; j > i; j--) | |

num[j] = num[j-1]; | |

num[i] = t; | |

k %= fact; | |

perm << to_string(num[i]); | |

} | |

return perm.str(); | |

} |

This time I’m shuffling elements around instead of erasing an element. Both of these operations have the same time complexity. The overall complexity in both cases in O(n^{2} + cn). Interestingly, interviewbit classifies this problem under backtracking, but we are not doing any backtracking. We directly hone in on the solution.