问题描述
我写的递归回溯算法找到一个给定的所有子集。
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重新$ P $的任何唯一的二进制串psents一组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.
在code在Java中:
The code in 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中你可以使用位集合,这使得code真短,但我用一个字节数组来说明这个过程更好。
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.
这篇关于如何编写迭代算法生成一组的所有子集?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!