Harry - 1 year ago 93
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 ?

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; }``

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download