在javascript中找到ith排列

Question

给定一个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;
}

如何修剪它只获得递归的一个分支？

Answer 1

您可以使用数组长度的阶乘作为帮助来获取所需的排列.

基本上,该算法计算数组的索引并重新组合结果.

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