生成数组中所有唯一组合的最佳方法是什么？

Question

假设我有以下数组：

const input = [“a”, “b”, “c”, “d”];

我想要创建这个输出：

[
  [“a”],
  [“a”, “b”],
  [“a”, “c”],
  [“a”, “d”],
  [“a”, “b”, “c”],
  [“a”, “b”, “d”],
  [“a”, “c”, “d”],
  [“a”, “b”, “c”, “d”],
  [“b”],
  [“b”, “c”],
  [“b”, “d”],
  [“b”, “c”, “d”],
  [“c”],
  [“c”, “d”],
  [“d”]
]

我不关心顺序或组合的长度，只需要所有在数组中唯一组合物品的各种方式。

在JavaScript中，最好的方法是什么？我认为有一个漂亮的递归解决方案，但迭代也可以做到。

此外，这个过程的正确技术术语是什么？

- jkhoffman

---

不，这不是排列。这里应该使用组合。 - ggorlen

抱歉，我没有看到任何排序。排列涉及顺序，组合涉及分组。这也不是笛卡尔积，因为我们只处理一个列表。OP想要 Python 的 [list(itertools.combinations("abcd", i)) for i in range(1, 5)] 的 JS 版本，但是要展开。应该有明显的重复问题，但是由于这些术语混淆，我总是找不到这个类别中的重复项。 - ggorlen

这个回答解决了你的问题吗？在数组中找到所有可能的子集组合？ - Nick

@ggorlen 找到了一个。只需要将基于最小长度为2的过滤更改为最小长度为1的过滤即可。我特别喜欢zovio对那个问题的回答。 - Nick

干得好。这个应该有一个重复项查找器徽章。 - ggorlen

Answer 1

正确的技术术语是幂集。以下是它的经典递归形式：

const f = (A, i=0) => i == A.length ? [[]] : f(A, i+1).flatMap(x => [x, [A[i]].concat(x)]);

console.log(JSON.stringify(f(['a', 'b', 'c', 'd'])));

- גלעד ברקן

---

或者类似地，const powerSet = ([x, ...xs]) => x == undefined ? [[]] : powerSet (xs) .flatMap (p => [p, [x, ...p]]) - Scott Sauyet

@ScottSauyet 这会使原始数组产生不必要的副本。 - גלעד ברקן

是的，每件事都有取舍。我的实现为了更优雅而牺牲了一些性能。你的实现为了默认参数的方便而牺牲了以某种方式调用它的能力（想想[set1, set2, set3].map(f)）。拥有多种选择是好的。 - Scott Sauyet

@ScottSauyet 哦，对了，你和我之前讨论过默认参数和 map。我想为此，我们需要一个包装器。 - גלעד ברקן

Answer 2

递归解法可能是最容易理解的，尽管我猜测还有其他更高效（在计算复杂度方面）的解决方案。

首先，数组中实际的元素并不重要，因此我们可以只使用它们的索引（0...n-1）进行计算，稍后我们通过 actualArray = indexArray.map(i => inputArray[i]) 将这些索引转换为实际元素。在下面的讨论中，我们假设索引存储在输出/结果中。

然后，由于组合中的顺序无关紧要，并且由于组合中的所有内容（索引）必须是唯一的，因此我们只需确保组合中的索引始终按升序排列。

因此，我们可以从只包含 1 个元素的组合（数组的数组）开始。在没有任何计算的情况下，我们都知道它们是：[[0]，[1]，[2]，[3]，... [n-1]]。我们可以编写代码来生成它们并将它们用作种子。

然后，对于基于已知包含 m 个元素的组合（数组的数组）找出所有包含 m+1 个元素的组合，我们可以执行以下操作：

1. 遍历所有由m个元素组成的组合（数组中的数组）
   1. 对于每个组合（长度为m的数组），
      1. 在范围（两端均包含）combination [combination.length-1]和n-1之间进行迭代，如果范围适用于查找下一个索引
         1. 复制原始数组并将新索引附加到其中。例如newCombination = [... combination, newIndex]。这是一个包含m + 1个元素的新组合。
         2. 将新发现的组合添加到结果中。
2. 现在我们已经找到了所有具有m + 1个元素的组合。它们可以用于找到所有具有m + 2个元素的组合。

我们可以一直这样做，直到找到包含n个元素的最后一个组合。

为了方便上述算法，内部数据结构可能是：

[
   [[0], [1], [2], ..., [n-1]],   // indexes of combinations with 1 elements
   [[0, 1], [0, 2], ..., [n-2, n-1]],  // indexes of combinations with 2 elements
   ...
   [[0, 2, ... n-1]],        // indexes of combinations with n elements
]

为了验证正确性，我们只需要检查以下内容：

• 组合的总数与我们通过数学计算得出的总数相同
• 在每个组合中，元素始终按升序排列
• 没有重复的组合（将combination.join（'，'）添加到Set可能很方便）

顺便说一下，这只是我的想法，我还没有用任何真实的代码或数据进行验证 :-)

- James Hu

---

我投票支持这个详细的、叙述性的答案，因为它有助于编写我的代码。 - Bluebird45