Given a set of ‘n’ elements, find their Kth permutation. Consider the following set of elements:

All permutations of the above elements are (with ordering):

Here we need to find the Kth permutation

- Recursion
- Factorial

void find_kth_permutation( vector<char>& v, int k, string& result) { //TODO: Write - Your - Code }

int factorial(int n) { if (n == 0 || n == 1) return 1; return n * factorial(n -1 ); } void find_kth_permutation( vector<char>& v, int k, string& result) { if (v.empty()) { return; } int n = (int)(v.size()); // count is number of permutations starting with each digit int count = factorial(n - 1); int selected = (k - 1) / count; result += v[selected]; v.erase(v.begin() + selected); k = k - (count * selected); find_kth_permutation(v, k, result); } string get_permutation(int n, int k) { vector<char> v; for (char i = 1; i <= n; ++i) { v.push_back(i + '0'); } string result; find_kth_permutation(v, k, result); return result; } int main(int argc, char* argv[]) { for (int i = 1; i <= factorial(4); ++i) { cout << i << "th permutation = " << get_permutation(4, i) << endl; } }

Linear, O(n).

Linear, O(n).

Recursive solution will consume memory on the stack.

Here is the algorithm that we will follow:

```
If input vector is empty return 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 selected element to result vector and remove it from original input vector
Deduce from k the blocks that are skipped i.e k = k - selected*block_size and goto step 1
```