Search⌘ K
AI Features
Home
Courses
Coderust: Hacking the Coding Interview

Find kth Permutation

Explore how to determine the kth permutation of a sequence of n elements by understanding the factorial concept and applying a recursive strategy to select elements in blocks. This lesson guides you to optimize the search for permutations beyond naive generation, helping you implement a linear time solution with clear mathematical reasoning.

We'll cover the following...

Statement

Given two numbers nn and kk, find kth^{th} permutation of nn. For n=3n = 3, all permutations are (with ordering):

g array 1st 123 2nd 132 3rd 213 4th 231 5th 312 6th 321

Sample input

Here 4 is the number nn and 8 is the kth^{th} permutation to be calculated.

4, 8

Expected output

2143

We need to find the kth^{th} permutation here.

Try it yourself

#include <string>
#include <vector>
#include <iostream>
using namespace std;
string GetPermutation(int n, int k) {
	//TODO: Write - Your - Code
	return "-1";
}

Solution

Let’s discuss a few basics first. We know that n!n! is the number of permutations for a set of size nn. Another obvious and important concept is that if we choose an element for the first position, then the total permutations of the remaining elements are (n−1)!(n-1)!.

For example, if we are given the elements {1, 2, 3, 4}, and we pick 1 as our first element, then for the remaining elements, we have the following permutations:

g array 234 243 324 342 423 432 a1 1 a1->array:e1

It is equal to 66 which we found with (n−1)!(n-1)!. This number is the same even if we pick another element for the first slot.

g array     234           6      ... ...     134           6      ... ...     124           6      ... ...     123           6      ... ... a1 1 a1->array:e1 a2 2 a2->array:e4 a3 3 a3->array:e7 a4 4 a4->array:e10

Naive solution:

  • A naive way of finding the kthk^{th} permutation will be to find all permutations and then return the kthk^{th} permutation.

  • Another way to say this is to maintain a running count of permutations seen so far and return once the kthk^{th} permutation is reached.

Optimized solution:

  • We can do better, if we look closely at the diagram above. If we are given kk and we somehow guess which block it’s going to lie in, that will help us find at least the first element.
  • Similarly, within that block, if we can identify a sub-block where kk resides, it will help us find the second element. We can do this recursively until we run out of options. Here is a visual representation of this approach if k=8k = 8:
g array 6   1...    1... 6   2...    2... 6   3...    3... 6   4...    4... array2 2   1..    1.. 2   3..    3.. 2   4..    4.. array:e4->array2:d1 k=2 a2 8th a2->array:d4 k=8 array3 1   3.    1   4.    array2:e1->array3:d2 k=2 solution 8th permutation is 2 1 4 3 array4 1   3    array3:e2->array4:d1 k=1

Here is the algorithm, we will follow:​

If the input vector is empty return the result vector

block_size = (n-1)! ['n' is the size of vector]
Figure out which block k will lie in and select the first element of that block
(this can be done by doing (k-1)/block_size )

Append a selected element to the result vector and remove it from the original input vector

Deduce from k the blocks that are skipped, i.e, k = k - selected*block_size, and goto step 1

Let’s understand this example with k=8k = 8 step by step below:

#include <string>
#include <vector>
#include <iostream>
using namespace std;
int factorial(int n) {
	if (n == 0 || n == 1) return 1;
	return n * factorial(n - 1);
}
void FindKthPermutation(vector<char>& v, int k, string& result,
						vector<int>& factorial) {
	if (v.empty()) {
		return;
	}
	int n = (int)(v.size());
	// factorial is the number of permutations starting with first digit
	// selected is the number of digits in permutation
	int selected = (k - 1) / factorial[n - 1];
	// Getting the first digit from selected array
	result += v[selected];
	v.erase(v.begin() + selected);
	k = k - (factorial[n - 1] * selected);
	// Recursively calling itself
	FindKthPermutation(v, k, result, factorial);
}
string GetPermutation(int n, int k) {
	vector<char> v;
	// Constructing the permutation number
	char c = '1';
	for (char i = 1; i <= n; ++i) {
		v.push_back(c);
		c++;
	}
	vector<int> factorial;
	for (int i = 0; i < n; i++) {
		if (i == 0 || i == 1) {
			factorial.push_back(1);
		} else {
			factorial.push_back(i * factorial[i - 1]);
		}
	}
	string result = "";
	FindKthPermutation(v, k, result, factorial);
	return result;
}
int main() {
	cout << "1. 2nd permutation of 12 = " << GetPermutation(2, 2) << endl;
	cout << "\n------------------------------------------------------------------------------------------------------\n" << endl;
	cout << "2. 5th permutation of 12 = " << GetPermutation(3, 5) << endl;
	cout << "\n------------------------------------------------------------------------------------------------------\n" << endl;
	cout << "3. 8th permutation of 1234 = " << GetPermutation(4, 8) << endl;
}

Time complexity

The time complexity of this solution is linear, O(n2)O(n^{2}), because we use memoization to avoid re-calculation of factorial values.

Space complexity

The space complexity of this solution is linear, O(n)O(n).