3

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

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;
    }
}

现在我们必须以迭代的形式编写相同的算法，该怎么做？

4

4 回答 4

13

您可以使用二进制计数器方法。任何长度为 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，这使得代码确实更短，但我使用字节数组来更好地说明该过程。

于 2014-03-09T08:59:04.630 回答
8

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

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

  • 如果我们看一下上面用于以二进制计数的变量，每个位置的数字可以被认为是一个标志，指示集合中相应索引处的元素是否应该包含在这个子集中。只需循环每个位（将余数除以 2，然后除以 2），包括输出中的相应元素。

例子：

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

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

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

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

然后3 = 00011，表明最后两个元素将被包含 - 输出{4,5}。

依此类推，一直到31 = 11111，表示将包含所有元素 - 输出{1,2,3,4,5}。

{1}* 实际上在代码方面00001，考虑到第一个余数 2 将对应于第 0 个元素、第二个余数、第一个元素等的标志，将其打开它的头输出会更简单，但是出于说明目的，上述内容更简单。

更一般地，任何递归算法都可以更改为迭代算法，如下所示：

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

  • 创建一个堆栈，其中每个元素都包含函数中每个必要的局部变量，以及我们正在忙于哪个部分的指示

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

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

  • return用适当的break语句替换

于 2014-03-09T09:19:52.597 回答
4

乔治算法的一个小 Python 实现。也许它会帮助某人。

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}
于 2015-01-25T10:47:57.627 回答
1

基本上你想要的是 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 次。您可以稍后使用此信息来优化算法。为了生成大小的组合，我提出的算法如下：

假设 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
 }
于 2014-03-09T09:14:11.970 回答