how to write iterative algorithm for generate all subsets of a set?

Question

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 ?

Solution 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.

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

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.

Solution 2

There are a few ways to write an iterative algorithm for this problem. The most commonly suggested would be to:

• Count (i.e. a simply for-loop) from 0 to 2numberOfElements - 1

• If we look at the variable used above for counting in binary, the digit at each position could be thought of a flag indicating whether or not the element at the corresponding index in the set should be included in this subset. Simply loop over each bit (by taking the remainder by 2, then dividing by 2), including the corresponding elements in our output.

Example:

Input: {1,2,3,4,5}.

We'd start counting at 0, which is 00000 in binary, which means no flags are set, so no elements are included (this would obviously be skipped if you don't want the empty subset) - output {}.

Then 1 = 00001, indicating that only the last element would be included - output {5}.

Then 2 = 00010, indicating that only the second last element would be included - output {4}.

Then 3 = 00011, indicating that the last two elements would be included - output {4,5}.

And so on, all the way up to 31 = 11111, indicating that all the elements would be included - output {1,2,3,4,5}.

* Actually code-wise, it would be simpler to turn this on its head - output {1} for 00001, considering that the first remainder by 2 will then correspond to the flag of the 0th element, the second remainder, the 1st element, etc., but the above is simpler for illustrative purposes.

---

More generally, any recursive algorithm could be changed to an iterative one as follows:

• Create a loop consisting of parts (think switch-statement), with each part consisting of the code between any two recursive calls in your function

• Create a stack where each element contains each necessary local variable in the function, and an indication of which part we're busy with

• The loop would pop elements from the stack, executing the appropriate section of code

• Each recursive call would be replaced by first adding it's own state to the stack, and then the called state

• Replace return with appropriate break statements

Solution 3

A little Python implementation of George's algorithm. Perhaps it will help someone.

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}

Solution 4

Basically what you want is P(S) = S_0 U S_1 U ... U S_n where S_i is a set of all sets contained by taking i elements from S. In other words if S= {a, b, c} then S_0 = {{}}, S_1 = {{a},{b},{c}}, S_2 = {{a, b}, {a, c}, {b, c}} and S_3 = {a, b, c}.

The algorithm we have so far is

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

We know that |S_i| = nCi where |S| = n. So basically we know that we will be looping nCi times. You may use this information to optimize the algorithm later on. To generate combinations of size i the algorithm that I present is as follows:

Suppose S = {a, b, c} then you can map 0 to a, 1 to b and 2 to c. And perumtations to these are (if i=2) 0-0, 0-1, 0-2, 1-0, 1-1, 1-2, 2-0, 2-1, 2-2. To check if a sequence is a combination you check if the numbers are all unique and that if you permute the digits the sequence doesn't appear elsewhere, this will filter the above sequence to just 0-1, 0-2 and 1-2 which are later mapped back to {a,b},{a,c},{b,c}. How to generate the long sequence above you can follow this algorithm

 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
 }

View more solutions