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

本文介绍了如何编写迭代算法来生成集合的所有子集?的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

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

I wrote recursive backtracking algorithm for finding all subsets of a given set.

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

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

now we have to write the same algorithm but in an iterative form, how to do it ?

推荐答案

您可以使用二进制计数器方法.任何长度为 n 的唯一二进制字符串表示一组 n 个元素的唯一子集.如果以 0 开头并以 2^n-1 结尾，则涵盖了所有可能的子集.计数器可以很容易地以迭代的方式实现.

You can use the binary counter approach. Any unique binary string of length n represents a unique subset of a set of n elements. If you start with 0 and end with 2^n-1, you cover all possible subsets. The counter can be easily implemented in an iterative manner.

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，这使代码确实更短，但我使用字节数组更好地说明了该过程.

Note that in Java one can use BitSet, which makes the code really shorter, but I used a byte array to illustrate the process better.