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:

Blogroll

Follow this blog by Email

Popular Posts