/***
 * The set [1,2, 3 ... ,n] contains a total of n! unique permutations.
 *
 * By listing and labeling all of the permutations in order,
 * We get the following sequence (ie, for n = 3):
 *
 * "123"
 * "132"
 * "213"
 * "231"
 * "312"
 * "321"
 * Given n and k, return the kth permutation sequence.
 *
 * Note: Given n will be between 1 and 9 inclusive.
 */
import java.util.Arrays;
public class PermutationSequence {
    public String getPermutation(int n, int k) {
        int A[] = new int[n];
        for (int i = 0; i < n; i++)
            A[i] = i + 1;
        while(--k != 0)
            getNext(A);
        StringBuffer sb = new StringBuffer();
        for (int i = 0; i < n; i++)
            sb.append(A[i]);
        return sb.toString();
    }
    private void getNext(int [] A) {
        int i;
        for (i = A.length - 1; i > 0; i--)
            if (A[i] > A[i - 1]) break;
        int k = i - 1;
        for (; i < A.length; i++) {
            if (A[i] <= A[k]) break;
        }
        int p = i - 1;
        int temp = A[k];
        A[k] = A[p];
        A[p] = temp;
        // sort right of k
        Arrays.sort(A, k + 1, A.length);
    }

    public static void main (String args[] ) {
        PermutationSequence ps = new PermutationSequence();
        String s = ps.getPermutation(3, 5);
        System.out.printf("S for n = 3, k = 5 is : %s \n", s);
    }
}

@@ -414,16 +414,97 @@
 uence %7B%0A
+    // Solution 1: Brute Force, or force enumeration.%0A    // O(n!)?, O(n)%0A    /*%0A
     publ
@@ -1235,16 +1235,933 @@
 );%0A    %7D
+%0A    */%0A%0A    // Solution 2: O(n) O(1)%0A    // Suppose the Kth permutation is a1, a2, a3, a4 ... an;%0A    // then:%0A    // a1 = k / (n - 1)!; k2 = k %25 (n - 1)!%0A    // a2 = k2 / (n - 2)!; k3 = r1 %25 (n - 2)!%0A    // ...%0A    // a(n-1) = k(n-1) / 1!; k(n) = k(n-1) %25 1;%0A    // a(n) = 0%0A    public String getPermutation(int n, int k) %7B%0A        char%5B%5D arr = new char%5Bn%5D;%0A        int pro = 1;%0A        for (int i = 0; i %3C n; i++) %7B%0A            arr%5Bi%5D = (char) ('1' + i);%0A            pro *= (i + 1);%0A        %7D%0A        k = k - 1;%0A        k %25= pro;%0A        pro /= n;%0A        for (int i = 0; i %3C n - 1; i++) %7B%0A            int selectI = k /pro;%0A            k = k %25 pro;%0A            pro /= (n - i - 1);%0A            int temp = arr%5BselectI + i%5D;%0A            for (int j = selectI; j %3E 0; --j) %7B%0A                arr%5Bi + j%5D = arr%5Bi + j - 1%5D;%0A            %7D%0A            arr%5Bi%5D = (char) temp;%0A        %7D%0A        return String.valueOf(arr);%0A    %7D
 %0A%0A    pu

add PermutationSequence.java