如何编写迭代算法来生成一个集合的所有子集？

Question

我编写了递归回溯算法来查找给定集合的所有子集。

void backtracke(int* a, int k, int n)
{
    if (k == n)
    {
        for(int i = 1; i <=k; ++i)
        {
            if (a[i] == true)
            {
                std::cout << i << " ";
            }
        }
        std::cout << std::endl;
        return;
    }
    bool c[2];
    c[0] = false;
    c[1] = true;
    ++k;
    for(int i = 0; i < 2; ++i)
    {       
        a[k] = c[i];
        backtracke(a, k, n);
        a[k] = INT_MAX;
    }
}

现在我们需要写出相同的算法，但以迭代形式进行，该如何做呢？

- user1886376

---

用循环和栈替代递归。 - amit

示例代码，请。 - user1886376

Answer 1

您可以使用二进制计数器的方法。任何长度为 n 的唯一二进制字符串都代表着一个有 n 个元素的集合中的独特子集。如果你从 0 开始，到 2^n-1 结束，你就覆盖了所有可能的子集。计数器可以很容易地以迭代的方式实现。

Java代码：

  public static void printAllSubsets(int[] arr) {
    byte[] counter = new byte[arr.length];

    while (true) {
      // Print combination
      for (int i = 0; i < counter.length; i++) {
        if (counter[i] != 0)
          System.out.print(arr[i] + " ");
      }
      System.out.println();

      // Increment counter
      int i = 0;
      while (i < counter.length && counter[i] == 1)
        counter[i++] = 0;
      if (i == counter.length)
        break;
      counter[i] = 1;
    }
  }

请注意，在Java中可以使用BitSet，这会使代码变得更短，但为了更好地说明过程，我使用了字节数组。

- Eyal Schneider

Answer 2

有几种方法可以为这个问题编写迭代算法。最常建议的方法是：

• 从0到2numberOfElements-1进行计数（即简单的for循环）

• 如果我们看一下上面用于计数的变量，每个位置上的数字都可以被视为指示相应索引处的元素是否应包含在该子集中的标志。简单地通过取模运算得出每个位（然后除以2），并将相应的元素包含在输出中。

例子：

输入：{1,2,3,4,5}。

我们从0开始计数，它在二进制中的表示是00000，这意味着没有设置标志，因此不包括任何元素（如果您不想要空子集，则显然会跳过此步骤）- 输出{}。

然后1 = 00001，表示只包括最后一个元素 - 输出{5}。

然后2 = 00010，表示只包括倒数第二个元素 - 输出{4}。

然后3 = 00011，表示包括最后两个元素 - 输出{4,5}。

一直到31 = 11111，表示所有元素都被包括 - 输出{1,2,3,4,5}。

* 实际上，从代码角度来看，将其反过来会更简单-对于00001输出{1}，因为第一个取模运算就对应于第0个元素的标志，第二个余数对应于第一个元素等等，但是以上方法更简单易懂。

---

更普遍地，可以将任何递归算法转换为迭代算法，如下所示：

• 创建一个循环，由几部分（类似于switch语句）组成，每个部分由函数中任意两个递归调用之间的代码组成

• 创建一个堆栈，每个元素都包含函数中每个必要的局部变量以及正在处理的部分的指示

• 循环将从堆栈中弹出元素，并执行相应的代码部分

• 每个递归调用将被替换为首先将自己的状态添加到堆栈中，然后再添加被调用的状态

• 用适当的break语句替换return

- Bernhard Barker

Answer 3

一个简单的 Python 实现 George 算法。也许可以帮助有需要的人。

def subsets(S):
    l = len(S)
    for x in range(2**l):
        yield {s for i,s in enumerate(S) if ((x / 2**i) % 2) // 1 == 1}

- Misha Tavkhelidze

Answer 4

基本上，你想要的是 P(S) = S_0 U S_1 U ... U S_n，其中 S_i 是从 S 中取 i 个元素所包含的所有集合的集合。换句话说，如果 S = {a, b, c}，则 S_0 = {{}}, S_1 = {{a},{b},{c}}，S_2 = {{a, b}, {a, c}, {b, c}}，S_3 = {a, b, c}。

到目前为止，我们拥有的算法如下：

set P(set S) {
    PS = {}
    for i in [0..|S|]
        PS = PS U Combination(S, i)
    return PS
}

我们知道 |S_i| = nCi，其中 |S| = n。因此，基本上我们知道我们将循环 nCi 次。您可以使用此信息以后优化算法。要生成大小为 i 的组合，我提出的算法如下：

假设 S={a,b,c}，那么您可以将 0 映射到 a，将 1 映射到 b，将 2 映射到 c。而这些的排列是（如果 i=2）0-0，0-1，0-2，1-0，1-1，1-2，2-0，2-1，2-2。要检查一个序列是否是一个组合，您需要检查数字是否都唯一，并且如果重新排列数字，该序列不会出现在其他地方，这将把上述序列过滤为只有 0-1、0-2 和 1-2，它们随后被映射回 {a,b}，{a,c}，{b,c}。如何生成上面的长序列，您可以按照以下算法进行。

 set Combination(set S, integer l) {
     CS = {}
     for x in [0..2^l] {
         n = {}
         for i in [0..l] {
             n = n U {floor(x / |S|^i) mod |S|} // get the i-th digit in x base |S|
         }
         CS = CS U {S[n]}
     }
     return filter(CS) // filtering described above
 }

- george