给定一个大小为arr的数组n，并且索引0<=i<n!我想要返回第i个排列。
我能够编写一个获取所有排列的方法：
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;
}
如何修剪它只获得递归的一个分支？
您可以使用数组长度的阶乘作为帮助程序来获取目标排列。基本上，该算法计算重新组合结果的数组索引。
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 %= 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; }这是计算成本较低的答案：使用布尔标志数组跟踪使用过的元素。它可能看起来似乎没什么改进，因为您仍然需要扫描标志数组以获取您正在寻找的元素，从而产生O（N ^ 2）性能。但是，如果您利用数组中元素的布局，您可能会得到一些改进：
function getN(n, array) {
var f,
l = array.length,
indices = [];
//Instead of using splice() to remove elements that are
//already in the permutation, I'll use an array of bit flags
//to track used elements.
var indexMask = [];
indexMask.length = array.length;
var indexMaskInit = 0;
for(indexMaskInit = 0; indexMaskInit < indexMask.length;
indexMaskInit++) {
indexMask[indexMaskInit] = true;
}
array = array.slice();
while(l--) {
f = factorial(l);
indices.push(Math.floor(n / f));
n %= f;
}
var toReturn = [];
toReturn.length = array.length;
//Now, extract the elements using the array of indices.
var numUsed;
for(numUsed = 0; numUsed < indices.length; numUsed++) {
//factIndex is the index in the set of elements that have
//not been selected yet.
var factIndex = indices[numUsed];
var elementFound = false;
//This code searches for the element by assuming that some
//elements have already been selected. The number of used
//elements can be found using the index of the outer loop.
//By counting the number of used elements at the beginning
//of the array, it may be possible to calculate an offset
//that can be used to find the desired element.
if(factIndex > 2 * numUsed)
{
var offset = 0, scanIndex;
//Boundary condition: no elements have been used yet,
//in which case we can use factIndex directly.
if(numUsed === 0) {
elementFound = true;
}
else {
//Loop to 2*numUsed, to avoid a linear search.
for(scanIndex = 0; scanIndex < 2 * numUsed;
scanIndex++) {
if(!indexMask[scanIndex]) {
offset++;
}
//Boundary condition: all used elements have
//been found.
if(offset >= numUsed) {
elementFound = true;
break;
}
}
}
if(elementFound) {
factIndex += offset;
}
}
//This code starts at the end of the array and counts the
//number of used elements.
else if ((indices.length - 1 - factIndex) > 2 * numUsed) {
var offset = 0, scanIndex;
//Boundary condition: no elements have been used yet,
//in which case we can use factIndex directly.
if(numUsed === 0) {
elementFound = true;
}
else {
var n = indices.length - 1;
//Loop to 2*numUsed, to avoid a linear search.
for(scanIndex = n; scanIndex > n - 2 * numUsed;
scanIndex--) {
if(!indexMask[scanIndex]) {
offset++;
}
//Boundary condition: all used elements have
//been found.
if(offset >= numUsed) {
elementFound = true;
break;
}
}
}
if(elementFound) {
factIndex += (numUsed - offset);
}
}
//If the number of used elements is not much greater than
//factIndex, or they do not all cluster at the beginning
//of the array, it may be better to run a linear search.
if(!elementFound)
{
var searchIndex = 0, i;
for(i = 0; i < indexMask.length; i++) {
if(indexMask[i]) {
if(searchIndex >= factIndex) {
break;
}
else {
searchIndex++;
}
}
}
factIndex = i;
}
toReturn[numUsed] = array[factIndex];
indexMask[factIndex] = false;
}
return toReturn;
}
function factorial(num) {
var result = 1;
while (num) {
result *= num;
num--;
}
return result;
}
var i, l;
var array = [1, 2, 3, 4];
//var array = ["a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o", "p", "q", "r", "s", "t", "u", "v", "w", "x", "y", "z"];
for (i = 0, l = factorial(array.length); i < l; i++) {
console.log(i, getN(i, array).join(' '));
}
尝试（来自here的算法）
function perm(n,arr) {
let r=[],i=1;
while (n) { r.unshift(n%i); n=n/i++|0 }
let s= i-1 ? arr.splice(-r.length) : arr;
return arr.concat(r.map( x=> s.splice(x,1)[0] ));
}
// TEST
for(let i=0; i<4*3*2*1; i++) console.log( i, perm(i,[1,2,3,4]).join() );