How can I generate all possible subsets of a binary string?

Question

I have a problem, 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

Magic - involves a bitmask:

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, although it is a bit more complex, with a binary string.

Answer 2

Nevermind - Damn it, I forgot that you had it in a string, not in int / long / whatever. You can still use the same logic, though ... Just count in binary format, but use only positions containing 1.

Just think out loud.

Take line 1001

, , 1001, 1000, 0001 0000, ?

, , "" .

-

orig = n;

while(n--)

, 1 0:

    if(n & !orig)
        continue;

, - 1, . , , 1000 1001

, 1, ? 000 111

:

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

:

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

, , 1, 1 1 .

- , :)

, - .

Answer 3

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

:

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

:

• , - '00000...'
• 1 : .

, .

Answer 5

• If you only need values ​​that are below the numeric value of the binary string, continue to select one of the binary string until you get 0.
• If you need all the values ​​that can be represented by this number of binary digits, subtract 1 from the largest number that can be represented by this number of digits until you reach 0.

This kind of question appears on those katcha code sites.