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 chunk = f / n;
        int prev = 0;
        int idx = 0;
        for (int i = 1; i <= f; i++) {
            if (prev < k && k <= (i * chunk)) {
                idx = i;
            }
            prev = i * chunk;
        }
        IntRef intRef = new IntRef();
        intRef.k = (idx-1) * chunk;
        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 <= 6; i++) {
            System.out.println(prob.getPermutation(3, i));
        }
        System.out.println(prob.getPermutation(7, 991));
    }
}

@@ -240,21 +240,23 @@
     int 
-chunk
+segment
  = f / n
@@ -273,122 +273,55 @@
 int 
-prev = 0;%0A        int idx = 0;%0A        for (int i = 1; i %3C= f; i++) %7B%0A            if (prev %3C k && k %3C= (i * chunk)
+idx = k / segment;%0A        if (k %25 segment != 0
 ) %7B%0A
@@ -336,63 +336,13 @@
     
-    
 idx
- = i;%0A            %7D%0A            prev = i * chunk
+++
 ;%0A  
@@ -420,13 +420,15 @@
 ) * 
-chunk
+segment
 ;%0A  
@@ -1499,24 +1499,141 @@
 roblem60();%0A
+//        for (int i = 1 ; i %3C= 9; i++) %7B%0A//            System.out.println(prob.getPermutation(i, 1));%0A//        %7D%0A//
         for 
@@ -1652,32 +1652,34 @@
  i %3C= 6; i++) %7B%0A
+//
             Syst
@@ -1717,24 +1717,26 @@
 ion(3, i));%0A
+//
         %7D%0A  
@@ -1725,32 +1725,81 @@
 ));%0A//        %7D%0A
+        long start = System.currentTimeMillis();%0A
         System.o
@@ -1833,15 +1833,140 @@
 ion(
-7, 991)
+8, 33856));%0A        System.out.println(prob.getPermutation(9, 94626));%0A        System.out.println(System.currentTimeMillis() - start
 );%0A 

Update problem 60