Problem
The set [1,2,3,…,n] contains a total of n! unique permutations.
Example
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.)
JavaScript Code
function getPermutation(n, k) { // initialize all numbers var numberList = []; for (var i = 1; i <= n; i++) { numberList.push(i); } // change k to be index k--; // set factorial of n var mod = 1; for (var i = 1; i <= n; i++) { mod = mod * i; } var result = ""; // find sequence for(var i = 0; i < n; i++) { mod = mod / (n - i); // find the right number(curIndex) of var curIndex = k / mod; // update k k = k % mod; // get number according to curIndex result += numberList[curIndex]; // remove from list numberList.splice(curIndex,1); } return result; }
0 comments:
Post a Comment