/*

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.

*/

// This is actually a n! base conversion

// At position i, we have i! values, and those values are from numbers [1...9] that

// hasn't been used in left positions.

// Maintain a StringBuilder to store the available numbers in ascending order

// The digit on i-th position is the index for number in StringBuilder

// O(n^2), delete a character from StringBuilder takes O(n) tme; space: O(10)

public class Solution {

public String getPermutation(int n, int k) {

if (n==0 || k==0) return "";

StringBuilder nums = new StringBuilder(), ret = new StringBuilder();

int base = 1;

for (int i=1; i<=n; i++){

nums.append(i);

base *= i;

}

k--;

while (n>0){

base /= n;

int numIndex = k/base;

k %= base;

ret.append(nums.charAt(numIndex));

nums.deleteCharAt(numIndex);

n--;

}

return ret.toString();

}

}

// use nextPermutation to iterate to the kth permutation

// time: O(n*nlgn); space: O(1)

public class Solution {

public String getPermutation(int n, int k) {

char[] p = new char[n];

for (int i=0; i<n; i++) p[i] = (char)(i+'1');

int len=1;

for (int i=1; i<=n; i++) len*=i;

k = k%len==0 ? len:k%len; // in case k is larger than the total number of sequence

for (int i=2; i<=k; i++){

nextPermutation(p);

}

return String.valueOf(p);

}

public void nextPermutation(char[] p){

int l = p.length - 1;

while (l > 0 && p[l - 1] > p[l]) l--;

Arrays.sort(p, l, p.length);

if (l == 0) return;

int i = l;

while (p[l-1] >= p[i] && i<p.length) i++;

char tmp = p[l-1];

p[l-1] = p[i];

p[i] = tmp;

}

}