查找分为两组的数字列表的所有可能组合

Question

我有一个号码列表，例如

120
233
197
400
276
356
121

出于我的程序的目的，这些数字必须分成两组。根据集合中的数字，程序计算每组的效率。然后它结合了两个集合的效率商数。然后将这两组及其效率商保存在一个数组中。

目标是找到两个集合都具有最高效率的集合组合。

我的问题：目前，我似乎无法全神贯注于检查每个可能的集合组合所需的算法。据我所知，它似乎需要一种递归形式。

如果您需要更多信息，请告诉我！提前致谢！

Answer 1

要遍历可以形成两个集合的所有可能方式，您应该遍历初始列表的所有可能子集。为此，您可以使用大小为 n 的位掩码，其中 n 是初始列表中的元素数。

要生成所有可能的大小为 n 的位掩码，您可以使用一个简单的循环（应该很容易移植到其他语言的 c++ 代码）：

for (int mask = 0; mask < (1 << (n - 1)); ++mask) {
  for (int i = 0; i < n; ++i) {
     if (mask & (1 << i)) {
       // element i is in the first sub set
     } else  {
       // element i is in the second sub set
     }
   }
   // compute efficiency quotient for these subsets
}

总体复杂度为 2ⁿ * efficiency_quotient 计算，除非您有关于效率商数的其他信息，否则您可以做到最好。

注意：这里我循环到 1 << (n - 1) 以避免考虑子集 A 和 B，然后再考虑 B 和 A。如果效率商关心顺序，则需要将其更改为 1 << n.

查找分为两组的数字列表的所有可能组合

Finding every possible combination of a list of numbers divided in two sets

algorithm

filtering

set