Problem of the day: kth permutation

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

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

k=4th 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 xth 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 kth 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 xth 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(cn2) 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(n2 + cn). Interestingly, interviewbit classifies this problem under backtracking, but we are not doing any backtracking. We directly hone in on the solution.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s