PermLex

package com.gokul.demo.InProgress;

public class PermutationLexi {

    public static void main(String[] args) {
        getPermutation(4, 10);
    }

    // public static List<List<Integer>> r = new LinkedList<>();
    public static String s = "";

    public static String getPermutation(int n, int k) {
        int[] nums = generateArray(n);
        backtrack(nums, 0, k);
        // System.out.println(s);
        return s;
        // System.out.println(r);
        // String s = "";
        // for (int m : r.get(k - 1)) {
        // s += String.valueOf(m);
        // }
    }

    static int c = 0;

    private static void backtrack(int[] nums, int i, int k) {

        if (i == nums.length) {
            if (++c == k) {
                for (int m : nums) {
                    s += String.valueOf(m);
                }
                System.out.println(s);
            }
        }
        for (int j = i; j <= nums.length - 1; j++) {
            rtRotate(nums, i, j);
            backtrack(nums, i + 1, k);
            ltRotate(nums, i, j);
        }
        // return s;

    }

    public static void rtRotate(int[] array, int start, int end) {
        reverse(array, start, end);
        reverse(array, start, start);
        reverse(array, start + 1, end);
    }

    public static void ltRotate(int[] array, int start, int end) {
        reverse(array, start, start);
        reverse(array, start + 1, end);
        reverse(array, start, end);
    }

    private static void reverse(int[] array, int start, int end) {
        while (start < end) {
            int temp = array[start];
            array[start] = array[end];
            array[end] = temp;
            start++;
            end--;
        }
    }

    public static int[] generateArray(int n) {
        int[] array = new int[n];
        for (int i = 0; i < n; i++) {
            array[i] = i + 1;
        }
        return array;
    }
}