如何创建元组式列表的排列，其中相同的整数对没有排列

Question

我有一个数组数组，其中内部数组是统一结构的("元组式"(，具有唯一ID(字符串(和非唯一整数：

[
["A",2], 
["B",1], 
["C",1]
]

我需要JavaScript函数来创建下面的排列列表，不会排列具有相同整数值的元组：

[
["A", "B", "C"],
["B", "A", "C"],
["B", "C", "A"]
]

在下面的评论中引用了用户pirchard的话，我试图"按第二个索引排列，避免重复"。

因此，该列表不应包括这些排列：

[
["A", "C", "B"], // integers same as in ["A", "B", "C"]
["C", "A", "B"], // integers same as in ["B", "A", "C"]
["C", "B", "A"]  // integers same as in ["B", "C", "A"]
]

此外，最好避免在阵列内部"移动"。因此，["A", "B", "C"]是比["A", "C", "B"]更好的置换

在最简单的场景中，输入可以是：

[
["A",1], 
["B",1], 
["C",1], 
["D",1]
]

结果应该只是1个置换，而不是24，这是同样置换相同整数的结果：

[
["A", "B", "C", "D"]
]

同样，应该避免阵列内部的"移动"，因此["A", "B", "C", "D"]是首选方案。

Answer 1

与其对字符数组进行操作，不如对字符组数组进行操作。您可以采用这些解决方案中的任何一个，而不是从输入中删除所选字符以将其放入输出中，而是删除所选组的第一个字符，并仅在组为空时删除该组。

function groupPermutations(groups) {
if (!groups.length) return [[]];
return groups.flatMap((group, i) => {
// assert(group.length > 0)
const [val, ...rest] = group;
const remaining = rest.length
? [...groups.slice(0,i), rest, ...groups.slice(i+1)]
: [...groups.slice(0,i), ...groups.slice(i+1)];
return groupPermutations(remaining).map(p => [val, ...p]);
});
}
console.log(groupPermutations(["A", "BC"]));
console.log(groupPermutations(["ABCD"]));

现在，您只需要将元组输入格式转换为分组即可：

const pairs = [
["A",2], 
["B",1], 
["C",1],
];
const byInteger = new Map();
for (const [val, key] of pairs) {
if (!byInteger.has(key)) byInteger.set(key, []);
byInteger.get(key).push(val);
}
const groups = Array.from(byInteger.values());
console.log(groupPermutations(groups));