具有最大长度参数的排列

Question

我正在编写一个函数来创建具有最大长度限制的所有可能的排列，数组中的每个项目只能使用一次。

原始排列代码如下：

function permutations(list)
{
// Empty list has one permutation
if (list.length == 0)
return [[]];
let result = [];
for (let i=0; i<list.length; i++)
{
// Clone list (kind of)
let copy = Object.create(list);
// Cut one element from list
let head = copy.splice(i, 1);
// Permute rest of list
let rest = permutations(copy);
// Add head to each permutation of rest of list
for (let j=0; j<rest.length; j++)
{
let next = head.concat(rest[j]);
result.push(next);
}
}
return result;
}

如何最好地添加此最大长度参数以创建唯一的组合结果？我添加了maxLength.但是在递归中，卡在何处最好地实现此参数。

Answer 1

从极简主义的角度来看，停止递归不是在你缩小列表的大小时，而是在从列表中取下maxLength元素时停止递归。

function permutations(list, maxLength)
{
// Empty list has one permutation
if (maxLength == 0)
return [[]];
let result = [];
for (let i=0; i<list.length; i++)
{
// Clone list (kind of)
let copy = Object.create(list);
// Cut one element from list
let head = copy.splice(i, 1);
// Permute rest of list
let rest = permutations(copy, maxLength-1);
// Add head to each permutation of rest of list
for (let j=0; j<rest.length; j++)
{
let next = head.concat(rest[j]);
result.push(next);
}
}
return result;
}
const maxLength = 4
console.time('by cp')
var r = permutations([1, 2, 3, 4, 5, 6], maxLength)
console.timeEnd('by cp')
console.log(r)

---

但是，一种类似但性能稍高的方法就是避免每次"尝试"都复制数组，而仅在找到解决方案时才复制数组

function permutations2(iList, maxLength)
{
const cur = Array(maxLength)
const results = []
function rec(list, depth = 0) {
if (depth == maxLength) {
return results.push(cur.slice(0))
}
for (let i = 0; i < list.length; ++i) {
cur[depth] = list.splice(i, 1)[0]
rec(list, depth + 1)
list.splice(i, 0, cur[depth])
}
}
rec(iList)
return results;
}
console.time('cp on solution')
var r = permutations2([1, 2, 3, 4, 5, 6], 4)
console.timeEnd('cp on solution')
console.log(r)