Harry - 9 months ago 68

Javascript Question

Given an array

`arr`

`n`

`0<i<n!`

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 Source

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