生成子集

时不时地，我会被涉及从给定对象集合中寻找最优子集的问题所挑战。几周前又发生了类似的情况。这个问题类似于背包问题（寻找总大小受限的物品中最有利的子集），而且……当然，我忘记了如何使用动态规划来解决它。但是，很多年前，我学到了一种非常简单的（容易记忆的）算法，它救了我一命，我将在本文中描述它。

《算法设计手册》，第453页将其定义为二进制计数。其背后的思想是 0 到 2^n-1（总数为 2ⁿ）之间的数字与长度为 n 的二进制字符串（总数为 2ⁿ）之间的一一映射，其中索引 i 处的位 1 表示“考虑原始集合中索引 i 处的对象，用于给定的子集”。我们还知道一个大小为 n 的集合的子集总数是 2ⁿ。到处都是 2ⁿ，太棒了！

让我们通过一个简单的例子来实际操作一下，一个小的集合 {A, B, C}，其中 n=3。我们对空集不感兴趣，因此我们将忽略第 0 次迭代，剩下总共 2³-1=7 个子集

迭代	二进制字符串	要考虑的对象的索引	子集
1	001	1	{A}
2	010	2	{B}
3	011	1 和 2	{A, B}
4	100	3	{C}
5	101	1 和 3	{A, C}
6	110	2 和 3	{B, C}
7	111	1, 2 和 3	{A, B, C}

我需要强调的是，这是一个指数级的（或 O(2ⁿ)）复杂度算法。它对于大型集合来说效率非常低。这里是一个代码示例

import java.util.LinkedHashSet;
import java.util.Set;

public class AllSubSets {
 public static void main(String args[]) {
  String[] setValues = new String[] { "A", "B", "C", "D", "E",
    "F", "G", "H", "I", "J" };

  long limit = 1 << setValues.length; // this is 2^length

  for (long l = 1; l < limit; l++) {
   Set<string> subSet = new LinkedHashSet<>();
   for (int i = 0; i < setValues.length; i++) {
    if ((l & (1 << i)) > 0) {
     subSet.add(setValues[i]);
    }
   }
   subSet.forEach(System.out::print);
   System.out.println();
  }
 }
}

以及结果

A
B
AB
C
AC
BC
ABC
D
... (trimmed due to the size) ...
CDEFGHIJ
ACDEFGHIJ
BCDEFGHIJ
ABCDEFGHIJ

细心的读者会立即回复说，这个版本仅限于最多 64 个对象的集合（在 Java 8 中，long 是 限制为 64 位，可以被视为无符号的）。BigInteger 支持按位运算，解决了这个限制。是的，额外的子集构造循环使其成为 O(n2ⁿ) 算法，但它仍然是指数级的。

然而，正如前面提到的，这并不是一个高效的算法。任何大于 64 个对象的集合都会产生超过 2⁶⁴ 个子集，这是一个很大的数字。即使是 2³² 尺寸也相当可观，所以不要将此算法用于大型集合。