gpt4 book ai didi

javascript - 在javascript中找到第i个排列

转载 作者:可可西里 更新时间:2023-11-01 01:29:48 25 4
gpt4 key购买 nike

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

如何 trim 它以仅获得递归的一个分支?

最佳答案

您可以使用数组长度的阶乘作为获取目标排列的助手。基本上,该算法计算数组索引,根据这些索引重新组合结果。

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

关于javascript - 在javascript中找到第i个排列,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/40441586/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com