the permutations with the same first number are in a group. you will realize there is n groups, each of (n−1)! numbers. The permutations in each group are sorted as they are as a universal group. So our algorithm can work as follows: find which group the k-th permutation belongs to, extract the common first number from the list of numbers and append it to the construction of the permutation, and iteratively find within that group the (((k−1)%(n−1)!)+1)-th permutation.
From http://fisherlei.blogspot.com/2013/04/leetcode-permutation-sequence-solution.html 那么这里，我们把a1去掉，那么剩下的permutation为 a2, a3, .... .... an, 共计n-1个元素。 n-1个元素共有(n-1)!组排列，那么这里就可以知道
In order to grow the tree, every time start the first unfixed element in each node, generate child nodes by swapping the first element with every other element. The leave node are those do not have element to swap.
Let’s start looking at the 2nd level. There are n 2nd nodes, each subtree of them has (n-1)! children. (there are n! permutation in total). So which 2nd level subtree the kth permutation locate in? We can find it by computingk / (n-1)!. Say it is the ith subtree, then we get to ith subtree and set k = k % (n-1)!. Do so recursively to search the subtree until we get the leave node.
public String getPermutation(int n, int k) {
int pos = 0;
List<Integer> numbers = new ArrayList<>(); // use linkedlist
int[] factorial = newint[n+1];
StringBuilder sb = new StringBuilder();
// create an array of factorial lookupint sum = 1;
factorial[0] = 1;
for(int i=1; i<=n; i++){
sum *= i;
factorial[i] = sum;
}
// factorial[] = {1, 1, 2, 6, 24, ... n!}// create a list of numbers to get indicesfor(int i=1; i<=n; i++){
numbers.add(i);
}
// numbers = {1, 2, 3, 4}
k--;
for(int i = 1; i <= n; i++){
int index = k/factorial[n-i];
sb.append(String.valueOf(numbers.get(index)));
numbers.remove(index);
k-=index*factorial[n-i];
}
return String.valueOf(sb);
}
public String getPermutation(int n, int k){
StringBuilder sb = new StringBuilder();
ArrayList<Integer> num = new ArrayList<Integer>();
int fact = 1;
for (int i = 1; i <= n; i++) {
fact *= i;
num.add(i);
}
for (int i = 0, l = k - 1; i < n; i++) {
fact /= (n - i);
int index = (l / fact);
sb.append(num.remove(index));
l -= index * fact;
}
return sb.toString();
}
staticint[] facts = newint[10];
static{
facts[1] = 1;
for (int i=2;i<=9;i++){
facts[i] = facts[i-1]*i;
}
}
public String getPermutation(int n, int k){
StringBuilder s = new StringBuilder();
List<Integer> digits = new LinkedList<Integer>();
for (int i=1;i<=n;i++){
digits.add(i);
}
k = k-1; //make zero based;while (k>0 && digits.size()>1){//k==0 means remaining digits in the list are ordered.int segmentLength = facts[digits.size()-1];
int index = k/segmentLength;
k = k%segmentLength; //calculate new k
s.append(digits.remove(index));
}
for (int i:digits){//add remaining digits
s.append(i);
}
return s.toString();
}
public String getPermutation(int n, int k){
int mod = 1;
List<Integer> candidates = new ArrayList<Integer>();
// 先得到n!和候选数字列表for(int i = 1; i <= n; i++){
mod = mod * i;
candidates.add(i);
}
// 将k先减1方便整除
k--;
StringBuilder sb = new StringBuilder();
for(int i = 0; i < n ; i++){
mod = mod / (n - i);
// 得到当前应选数字的序数int first = k / mod;
// 得到用于计算下一位的k
k = k % mod;
sb.append(candidates.get(first));
// 在列表中移出该数字
candidates.remove(first);
}
return sb.toString();
}
Another way is to calculate every digit. For example, assuming we are going to solve the problem when n = 3 and k = 5. In fact, because k starts from 1, we need to subtract 1 from it to make it starting from 0. So we are going to find the permutation 4 now. To calculate the first digit, we can calculate it by k % (n – 1)! = 4 / 2! = 2, which is the position of 3 in array [1,2,3]. Now we need to delete 3 from the array, so the array becomes [1, 2]. And k should become 4 % 2! = 0. Now we calculate k / (n – 2)! = 0 / 1 = 0, which is the position of 1 in array [1, 2]. So the second digit should be 1. We need to delete 1 from the array. And there is only one entry left in the array. So the final digit should be 2. Finally we get the permutation: 312.
publicString getPermutation(int n, int k){// initialize all numbers
ArrayList<Integer> numberList =new ArrayList<Integer>();for(int i =1; i <= n; i++){
numberList.add(i);}// change k to be index
k--;// set factorial of nint mod =1;for(int i =1; i <= n; i++){
mod = mod * i;}String result ="";// find sequencefor(int i =0; i < n; i++){
mod = mod /(n - i);// find the right number(curIndex) ofint curIndex = k / mod;// update k
k = k % mod;// get number according to curIndex
result += numberList.get(curIndex);// remove from list
numberList.remove(curIndex);}return result.toString();}
publicString getPermutation(int n, int k){boolean[] output =newboolean[n];
StringBuilder buf =new StringBuilder("");int[] res =newint[n];
res[0]=1;for(int i =1; i < n; i++)
res[i]= res[i -1]* i;for(int i = n -1; i >=0; i--){int s =1;while(k > res[i]){
s++;
k = k - res[i];}for(int j =0; j < n; j++){if(j +1<= s && output[j]){
s++;}}
output[s -1]=true;
buf.append(Integer.toString(s));}return buf.toString();}
public String getPermutation(int n, int k) {
List<Integer> participate = new ArrayList<>(n);
if (n <= 1) {
return"1";
}
for (int i = 1; i <= n; i++) {
participate.add(i);//build an initial list
}
return recur(n, k - 1, participate, new StringBuilder(n));//k-1 for get element from list
}
private String recur(int n, int k, List<Integer> participate, StringBuilder sb) {
if (n == 2) {
sb.append(participate.get(k));
participate.remove(k);
sb.append(participate.get(participate.size() - 1));
return sb.toString();
}
int x = fac(n); // x: sequence length Example: n = 5, there are 5 sequences start with 1 to 5, each sequence has 24 itemsint i = k / x; // i: which sequence the search k it belong. Example: n=4 k=8, i=(8-1)/6=1. so the start number should be 2
sb.append(participate.get(i));
participate.remove(i);
return recur(n - 1, k % x, participate, sb);
}
privateintfac(int n) {
int sum = 1;
for (int i = 1; i < n; i++) {
sum *= i;
}
return sum;
}
public static String getPermutation2(int n, int k) {
kth = k;
StringBuilder done = new StringBuilder();
StringBuilder rest = new StringBuilder();
for(int i=1; i<=n; i++){
rest.append(i);
}
rec(done, rest);
return save;
}
public static void rec(StringBuilder done, StringBuilder rest){
if(rest.length() == 0){
kth--;
if(kth == 0){
save = done.toString();
}
return;
}
for(int i=0; i<rest.length(); i++){
char c = rest.charAt(i);
rest.deleteCharAt(i);
done.append(c);
rec(done, rest);
done.deleteCharAt(done.length()-1);
http://blueocean-penn.blogspot.com/2015/11/permutation-sequence.html The best way to approach the problem is to divide and conquer: let's start with numbers 1, 2, 3, 4, and we can divide the sequences into 4 groups each starts with 1, 2, 3, 4, the number of sequences in each are 3!, k/3! will decide which group the kth sequence belongs to, saying k=9, k/3! = 1, so kth sequence belongs with group starts with 2.
now we have 1,3,4 and we should look for k%3!=9%6=3th sequence in this set
And we can use recursion to do divide and conquer work. public static List<Integer> permutationByRank(int n, int k){ //prepare the set List<Integer> list = new ArrayList<Integer>(); for(int i=1; i<=n; i++) list.add(i); //calculate the group size int size = factor(n-1); return permuByRankUtil(list, k-1, size); } /* * here k starts at 0 to n!-1 for easy computing purpose */ public static List<Integer> permuByRankUtil(List<Integer> nums, int k, int f){ int size = nums.size(); //base case if(size==1) return nums; else{ //decide group index int index = k/f; int first = nums.remove(index); List<Integer> re = permuByRankUtil(nums, k%f, f/(size-1)); re.add(0, first); return re; } } http://www.zrzahid.com/k-th-permutation-sequence/
// k is 1-basedpublic String getPermutation(int n, int k) {
int[] nums = getNums(n);
permute(nums, k-1);
return convertArrayToString(nums);
}
// k is 0-basedpublicvoidpermute(int[] nums, int k) {
int divisor = fact(nums.length-1);
for ( int i = 0; i <= nums.length-2; i++ ) {
int swapTime = k/divisor;
for ( int j = 1; j <= swapTime; j++ ) { swap(nums, i, i+j); }
k %= divisor; divisor /= nums.length-i-1;
}
}
// Helper Methodpublicintfact(int n) { return n <= 1 ? 1 : n*fact(n-1); }
publicvoidswap(int[] arr, int i, int j) { int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp; }
public String convertArrayToString(int[] arr){
StringBuffer s = new StringBuffer();
for ( int element : arr ) { s.append(element); }
return s.toString();
}
publicint[] getNums(int n) {
int[] nums = newint[n];
for ( int i = 0; i < nums.length; i++ ) { nums[i] = i+1; }
return nums;
}
