How do i generate all possible subsets of an binary string?

Question

Hi.. i have a problem, that i don't know how to solve it.

i have a binary string and i want to generate all possible binary substrings.

Example :

input : 10111
output: 10000, 10100,00111,00001,10110 ...

How can i do this , fast AND Smart ?

Answer 1

1. If you just want values that are below the numeric value of the binary string, keep taking one away from the binary string until you get to 0.
2. If you want all values that can be represented by that number of binary digits, subtract 1 from the highest number that can be represented by that number of digits until you get to 0.

This kind of question appears on those code katcha sites

Answer 2

Nevermind--damn I forgot you had it in a string and not a int/long/whatever. You can still use the same logic though... Just count in binary but only use the positions that contain 1's.

Just thinking aloud.

Let's take the string 1001

What you want, I think, is the four numbers 1001, 1000, 0001 and 0000, is that right?

If so, what you are doing is counting the "ones" positions.

One way is to store off your original number

orig = n;

and then start iterating over that and every lower number

while(n--)

but each iteration, ignore ones that attempt to put 1's in the 0's position:

    if(n & !orig)
        continue;

If you expect it to be sparse--as in a lot of zeros with very few 1's, you could use a shifting mechanism. So let's say your number is 1000 1001

Notice there are three 1's, right? So just count from 000 to 111

But for each iteration, spread the bits out again:

n & 0000 0001 | n << 2 & 0000 1000 | n << 5 & 1000 0000

or the other way to think about it:

n & 001 | (n & 010) * 1000 | (n & 100) * 1000 000

This could be slower than the other solution depending on how many 1's appear though since it involves an inner loop with 1 iteration for each 1 in the original number.

Sorry about shifting between binary and decimal--I can do it all in hex if you like :)

Right now I can't come up with a pattern that directly maps bits without shifting--that would work best.

Answer 3

Use recursion

printsubsets(const string &in, const string &out)
{
  if(in.empty())
  {
    cout<<out<<"\n";
    return;
  }

  if(in[0]=='1')
    printsubsets(in.substr(1), out+"1");
  printsubsets(in.substr(1), out+"0");
}

Answer 4

This does it:

vector<string> submasks(string in)
{
    vector<string> out;

    out.push_back(string(in.size(), '0'));

    for (int i = 0; i < in.size(); ++i)
    {
        if (in[i] == '0') continue;

        int n = out.size();
        for (int j = 0; j < n; ++j)
        {
            string s = out[j];
            s[i] = '1';
            out.push_back(s);
        }
    }

    return out;
}

The algorithm does this:

1. Start with a vector containing just an empty bit-string '00000...'
2. For each 1 in the input string: create a copy of each string in the output vector with that 1 set.

I think that's pretty much optimal.

Answer 5

Magic - assumes bitmask though:

subset( int x ) 
    list = ()
    for ( int i = x; i >= 0; i = ( ( i - 1 ) & x ) )
          list.append( i )
    return list

You can use the same logic, though it's a little bit more involved, with a binary string.