Harry Harry - 1 month ago 18
Javascript Question

Find ith permutation in javascript

Given an array

arr
of size
n
, and and index
0<i<n!
I want to return the ith permutation.

I was able to write a method that gets all permutations:

function permute (arr) {
var permutations = [];
if (arr.length === 1) {
return [ arr ];
}

for (var i = 0; i < arr.length; i++) {
var subPerms = permute(arr.slice(0, i).concat(arr.slice(i + 1)));
for (var j = 0; j < subPerms.length; j++) {
subPerms[j].unshift(arr[i]);
permutations.push(subPerms[j]);
}
}
return permutations;
}


How do I trim it to get only one branch of the recursion ?

Answer

You could use the factorial of the length of the array as helper for getting the wanted permutation.

Basically this algorithm calculates the indices of the array and reassembles the result upon.

function getN(n, array) {
    var f,
        l = array.length,
        indices = [];

    array = array.slice();
    while (l--) {
        f = factorial(l);
        indices.push(Math.floor(n / f));
        n -= Math.floor(n / f) * f;
    }
    return indices.map(function (i) {
        return array.splice(i, 1)[0];
    });
}

function factorial(num) {
    var result = 1;
    while (num) {
        result *= num;
        num--;
    }
    return result;
}

var i, l,
    array = [1, 2, 3, 4];

for (i = 0, l = factorial(array.length); i < l; i++) {
    console.log(i, getN(i, array).join(' '));
}
.as-console-wrapper { max-height: 100% !important; top: 0; }