package leetcode;

import java.util.HashSet;
import java.util.Set;

/**
 * https://leetcode.com/problems/permutation-sequence/
 */
public class Problem60 {
    public String getPermutation(int n, int k) {
        int f = factorial(n);
        int segment = f / n;
        int idx = k / segment;
        if (k % segment != 0) {
            idx++;
        }
        IntRef intRef = new IntRef();
        intRef.k = (idx-1) * segment;
        Set<Integer> set = new HashSet<>();
        set.add(idx);
        return getPermutation(n, k, n-1, intRef, set, "" + idx);
    }
    
    private static class IntRef {
        int k;
    }
    
    private String getPermutation(int n, int k, int m, IntRef intRef, Set<Integer> set, String accu) {
        if (m == 0) {
            intRef.k++;
            if (intRef.k == k) {
                return accu;
            }
            return null;
        }
        for (int i = 1; i <= n; i++) {
            if (!set.contains(i)) {
                Set<Integer> newSet = new HashSet<>(set);
                newSet.add(i);
                String result = getPermutation(n, k, m-1, intRef, newSet, accu+i);
                if (result != null) {
                    return result;
                }
            }
        }
        return null;
    }
    
    private int factorial(int n) {
        if (n == 1) {
            return n;
        }
        return n * factorial(n-1);
    }
    
    public static void main(String[] args) {
        Problem60 prob = new Problem60();
//        for (int i = 1 ; i <= 9; i++) {
//            System.out.println(prob.getPermutation(i, 1));
//        }
//        for (int i = 1 ; i <= 6; i++) {
//            System.out.println(prob.getPermutation(3, i));
//        }
        long start = System.currentTimeMillis();
        System.out.println(prob.getPermutation(8, 33856));
        System.out.println(prob.getPermutation(9, 94626));
        System.out.println(System.currentTimeMillis() - start);
    }
}

@@ -29,22 +29,24 @@
 va.util.
-HashSe
+ArrayLis
 t;%0Aimpor
@@ -57,18 +57,19 @@
 va.util.
-Se
+Lis
 t;%0A%0A/**%0A
@@ -152,20 +152,17 @@
 lem60 %7B%0A
-    
+%09
 public S
@@ -202,1357 +202,562 @@
 ) %7B%0A
-        int f = factorial(n);%0A        int segment = f / n;%0A        int idx = k / segment;%0A        if (k %25 segment != 0) %7B%0A            idx++;%0A        %7D%0A        IntRef intRef = new IntRef();%0A        intRef.k = (idx-1) * segment;%0A        Set%3CInteger%3E set = new HashSet%3C%3E();%0A        set.add(idx);%0A        return getPermutation(n, k, n-1, intRef, set, %22%22 + idx);%0A    %7D%0A    %0A    private static class IntRef %7B%0A        int k;%0A    %7D%0A    %0A    private String getPermutation(int n, int k, int m, IntRef intRef, Set%3CInteg
+%09%09int%5B%5D factorials = new int%5Bn%5D;%0A%09%09for (int i = 0; i %3C n; i++) %7B%0A%09%09%09factorials%5Bi%5D = factorial(i);%0A%09%09%7D%0A%09%09List%3CInteger%3E numbers = new ArrayList%3C%3E();%0A%09%09for (int i = 1; i %3C= n; i++) %7B%0A%09%09%09numbers.add(i);%0A%09%09%7D%0A%09%09StringBuild
 er
-%3E
  s
-et, String accu) %7B%0A        if (m == 0) %7B%0A            intRef.k++;%0A            if (intRef.k
+b = new StringBuilder();%0A%09%09for (int i = n-1; i %3E= 0; i--) %7B%0A%09%09%09int idx
  =
-=
  k
-) %7B%0A                return accu;%0A            %7D%0A            return null;%0A        %7D%0A        for (int i = 1; i %3C= n; i++) %7B%0A            if (!set.contains(i)) %7B%0A                Set%3CInteger%3E newSet = new HashSet%3C%3E(set);%0A                newSet.add(i);%0A                String result = getPermutation(n, k, m-1, intRef, newSet, accu+i);%0A                if (result != null) %7B%0A                    return result;%0A                %7D%0A            %7D%0A        %7D%0A        return null;%0A    %7D%0A    %0A    private int factorial(int n) %7B%0A        if (n == 1) %7B%0A            return n;%0A        %7D%0A        return n * factorial(n-1);%0A    %7D%0A    %0A    public static void main(String%5B%5D args) %7B%0A        Problem60 prob = new Problem60();%0A//        for (int i = 1 ; i %3C= 9; i++
+ / factorials%5Bi%5D;%0A%09%09%09if (k %25 factorials%5Bi%5D == 0) %7B%0A%09%09%09%09idx -= 1;%0A%09%09%09%7D%0A%09%09%09sb.append(numbers.get(idx));%0A%09%09%09numbers.remove(idx);%0A%09%09%09k = k - (idx * factorials%5Bi%5D);%0A%09%09%7D%0A%09%09return sb.toString();%0A%09%7D%0A%09%0A    private int factorial(int n) %7B%0A        if (n == 0 %7C%7C n == 1
 ) %7B%0A
-//
     
@@ -768,410 +768,60 @@
     
-System.out.println(prob.getPermutation(i, 1));%0A//        %7D%0A//        for (int i = 1 ; i %3C= 6; i++) %7B%0A//            System.out.println(prob.getPermutation(3, i));%0A//        %7D%0A        long start = System.currentTimeMillis();%0A        System.out.println(prob.getPermutation(8, 33856));%0A        System.out.println(prob.getPermutation(9, 94626));%0A        System.out.println(System.currentTimeMillis() - start
+return 1;%0A        %7D%0A        return n * factorial(n-1
 );%0A 

Solve problem 60 (finally!)