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:

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:

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.

### Like this:

Like Loading...

*Related*