# Problem Statement
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

<br>

# Hint
* Recursion
* Factorial

<br>

# Try  it yourself

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

#include <string>
#include <vector>
#include <iostream>
using namespace std;

class kth_permutation {
  static void find_kth_permutation(
      List<Character> v, 
      int k,
      StringBuilder result) {
    //TODO: Write - Your - Code
  } 
} 

import java.util.*;

class ListUtil{
  public static <T> boolean is_equal(List<T> v1, List<T> v2) {
    if(v1.size() != v2.size()){
      return false;
    }

    for(int i= 0 ; i < v1.size() ; i++) {
      if(!v1.get(i).equals(v2.get(i))) {
        System.out.println(v1.get(i) + "not equal" + v2.get(i));
        return false;
      }
    }

    return true;
  }

  /*public static booleaaan is_equal(List<Integer> v1, List<Integer> v2) {
    if(v1.size() != v2.size()){
      return false;
    }
    for(int i= 0 ; i < v1.size() && i < v2.size(); i++) {
      //System.out.print(String.format("\n%d-%d\n", v1.get(i),v1.get(i)));
      if(v1.get(i) - v2.get(i) != 0) {
        return false;
      }
    }
    System.out.print(String.format("\nTRUE\n"));
    return true;
  }*/

  public static void print(List<Integer> l) {
    for (Integer i : l) {
      System.out.print(i + ", ");
    }
    System.out.println();
  }

  public static ArrayList<Integer> createRandomList(int length) {
    ArrayList<Integer> l = new ArrayList<Integer>();
    for (int i = 1; i < length + 1; ++i) {
      l.add(i);
    }

    Collections.shuffle(l);
    return l;
  }

  public static List<Integer> create_random_list(int length, int max_value) {
    List<Integer> l = new ArrayList<Integer>();
    for (int i = 1; i < length + 1; ++i) {
      l.add(new Random().nextInt(max_value));
    }

    Collections.shuffle(l);
    return l;
  }
}

Java

def find_kth_permutation(v, k, result):
  #TODO: Write - Your - Code
  return result

def factorial(n):
  if n == 0 or n == 1:
    return 1
  return n * factorial(n -1 )

Python

let find_kth_permutation = function(v, k, result) {
  //TODO: Write - Your - Code
};

JavaScript

def find_kth_permutation(v, k, result)
   #TODO: Write - Your - Code
  return result[0]
end

def factorial(n)
  if (n == 0 || n == 1)
    return 1
  end
  return n * factorial(n - 1)
end

Ruby

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;
    }
}

class kth_permutation{
  static int factorial(int n) {
    if (n == 0 || n == 1) return 1;
    return n * factorial(n -1 );
  }

  static void find_kth_permutation(
      List<Character> v, 
      int k,
      StringBuilder result) {
  
    if (v.isEmpty()) {
      return;
    }
  
    int n = v.size();
    // count is number of permutations starting with first digit
    int count = factorial(n - 1);
    int selected = (k - 1) / count;
  
    result.append(v.get(selected));
    v.remove(selected);

    k = k - (count * selected);
    find_kth_permutation(v, k, result);
  }
  static String get_permutation(int n, int k) {
    List<Character> v = new ArrayList<Character>();
    char c = '1';
    for (int i = 1; i <= n; ++i) {
      v.add(c);
      c++;
    }
  
    StringBuilder result = new StringBuilder();
    find_kth_permutation(v, k, result);
    return result.toString();
  }
  public static void main(String[] args) {
    for (int i = 1; i <= factorial(4); ++i) {
      System.out.println( i + "th permutation = \t" + get_permutation(4, i));
    }
  }  
}  

def factorial(n):
  if n == 0 or n == 1:
    return 1
  return n * factorial(n -1 )

def find_kth_permutation(v, k, result):
  if not v:
    return
  
  n = len(v)
  # count is number of permutations starting with first digit
  count = factorial(n - 1)
  selected = (k - 1) // count
  
  result += str(v[selected])
  del v[selected]
  k = k - (count * selected)
  find_kth_permutation(v, k, result)
  
def get_permutation(n, k):
  v = list(range(1, n + 1))
  result = []
  find_kth_permutation(v, k, result)
  return ''.join(result)

def main():
  n = factorial(4)
  for i in range(1, n + 1):
    print(str(i) + "th permutation = \t", get_permutation(4, i))

main()

def factorial(n)
  if (n == 0 || n == 1)
    return 1
  end
  return n * factorial(n - 1)
end

def find_kth_permutation(v, k, result)
  if (!v || v.length == 0)
    return
  end

  n = v.length
  # count is number of permutations starting with first digit
  count = factorial(n - 1)
  selected = ((k - 1) / count).floor
  result[0] += '' + v[selected].to_s
  v = v - v.slice(selected, 1)
  k = k - (count * selected)

  find_kth_permutation(v, k, result)
end

def get_permutation(n, k)
  v = []
  for i in 0 .. n-1
    v.push(i + 1)
  end
  print v.to_s + "\n"
  result = ['']
  find_kth_permutation(v, k, result)
  return result[0]
end

def main()
  n = factorial(4)
  for i in 1 .. n
    puts i.to_s + "th permutation = " + get_permutation(4, i).to_s + "\n\n"
  end
end

main()

# Solution Explanation
## Runtime Complexity
Linear, O(n).

## Memory Complexity
Linear, O(n).

Recursive solution will consume memory on the stack.

<br>

## Solution Breakdown

Here is the algorithm that we will follow:

```html
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
```

> Practice problems like this and many more by checking out our [Grokking the Coding Interview: Patterns for Coding Questions](https://www.educative.io/courses/grokking-the-coding-interview) course!

Given a set of n elements find their kth permutation.

Find Kth Permutation

Problem Statement

Hint

Try it yourself

Solution

Solution Explanation

Runtime Complexity

Memory Complexity

Solution Breakdown