Find the K-th Permutation Sequence of first N natural numbers

// Java program to Find the kth Permutation
// Sequence of first n natural numbers
import java.util.*;

class GFG {
    // Driver code
    public static void main(String[] args)
    {
        int n = 3, k = 4;
        String kth_perm_seq = findKthPermutation(n, k);

        // function call
        System.out.println(kth_perm_seq);
    }

    static char[] swap(String s, int i, int j)
    {
        char[] ch = s.toCharArray();
        char temp = ch[i];
        ch[i] = ch[j];
        ch[j] = temp;
        return ch;
    }

    // recursive function to generate all
    // possible permutations of a string
    static void generate_permutations(String str, int idx,
                                      List<String> result)
    {
        // base case
        if (idx == str.length()) {
            result.add(str);
            return;
        }

        // traverse string from idx to end
        for (int i = idx; i < str.length(); i++) {
            str = new String(swap(str, i, idx));
            generate_permutations(str, idx + 1, result);
            str = new String(swap(str, i, idx));
        }
    }

    // Function to find the
    // kth permutation of n numbers
    static String findKthPermutation(int n, int k)
    {
        String str = "";
        List<String> result = new ArrayList<String>();

        // Insert all natural number
        // upto n in string
        for (int i = 1; i <= n; i++) {
            str += i;
        }
        generate_permutations(str, 0, result);

        // sort the generated permutations
        Collections.sort(result);

        // make k 0-based indexed to point to kth sequence
        return result.get(k - 1);
    }
}

// This code is contributed by Tapesh(tapeshdua420)

// Java program to Find 
// the kth Permutation
// Sequence of first 
// n natural numbers
import java.util.*;
class GFG{

// Function to find the index of
// number at first position of
// kth sequence of set of size n
static int findFirstNumIndex(int k, 
                             int n)
{
  if (n == 1)
    return 0;
  n--;

  int first_num_index;
  
  // n_actual_fact = n!
  int n_partial_fact = n;

  while (k >= n_partial_fact && n > 1) 
  {
    n_partial_fact = n_partial_fact * 
                     (n - 1);
    n--;
  }

  // First position of the
  // kth sequence will be
  // occupied by the number present
  // at index = k / (n-1)!
  first_num_index = k / n_partial_fact;

  k = k % n_partial_fact;
  return first_num_index;
}

// Function to find the
// kth permutation of n numbers
static String findKthPermutation(int n, 
                                 int k)
{
  // Store final answer
  String ans = "";

  HashSet<Integer> s = new HashSet<>();

  // Insert all natural number
  // upto n in set
  for (int i = 1; i <= n; i++)
    s.add(i);

  Vector<Integer> v = new Vector<>();
  v.addAll(s);

  // Mark the first position
  int itr = v.elementAt(0);
  
  // Subtract 1 to 
  // get 0 based 
  // indexing
  k = k - 1;

  for (int i = 0; i < n; i++) 
  {
    int index = findFirstNumIndex(k, 
                                  n - i);
    
    // itr now points to the
    // number at index in set s
    if(index < v.size()) 
    {
      ans += ((v.elementAt(index).toString()));
      v.remove(index);
    }
    else
      ans += String.valueOf(itr + 2);

    // Remove current number 
    // from the set
    itr = v.elementAt(0);
  }
  return ans;
}

// Driver code
public static void main(String[] args)
{
  int n = 3, k = 4;
  String kth_perm_seq = findKthPermutation(n, k);
  System.out.print(kth_perm_seq + "\n");
}
}

// This code is contributed by Rajput-Ji

public class KthPermutation {

    static class TreeNode {
        int val;
        TreeNode left, right;

        public TreeNode(int val) {
            this.val = val;
            this.left = this.right = null;
        }
    }

    static int[] fact = {1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880};

    static TreeNode insert(TreeNode root, int val) {
        if (root == null)
            return new TreeNode(val);
        if (val < root.val)
            root.left = insert(root.left, val);
        else
            root.right = insert(root.right, val);
        return root;
    }

    static TreeNode delete(TreeNode root, int val) {
        if (root == null)
            return null;
        if (val < root.val)
            root.left = delete(root.left, val);
        else if (val > root.val)
            root.right = delete(root.right, val);
        else {
            if (root.left == null)
                return root.right;
            else if (root.right == null)
                return root.left;
            root.val = minValue(root.right);
            root.right = delete(root.right, root.val);
        }
        return root;
    }

    static int minValue(TreeNode root) {
        int minv = root.val;
        while (root.left != null) {
            minv = root.left.val;
            root = root.left;
        }
        return minv;
    }

    static int findKthSmallest(TreeNode root, int k) {
        if (root == null)
            return -1;
        int leftCount = countNodes(root.left);
        if (k == leftCount + 1)
            return root.val;
        if (k <= leftCount)
            return findKthSmallest(root.left, k);
        return findKthSmallest(root.right, k - leftCount - 1);
    }

    static int countNodes(TreeNode root) {
        if (root == null)
            return 0;
        return 1 + countNodes(root.left) + countNodes(root.right);
    }

    static String getPermutation(int n, int k) {
        TreeNode root = null;
        for (int i = 1; i <= n; i++)
            root = insert(root, i);

        StringBuilder str = new StringBuilder();
        for (int i = 0; i < n; i++) {
            int index = (k - 1) / fact[n - i - 1] + 1;
            int val = findKthSmallest(root, index);
            str.append(val);
            root = delete(root, val);
            k = k - (index - 1) * fact[n - i - 1];
        }
        return str.toString();
    }

    public static void main(String[] args) {
        int n = 3, k = 4;
        String kth_perm_seq = getPermutation(n, k);
        System.out.println(kth_perm_seq);  // Output: 231
    }
}