Как мне сгенерировать все возможные подмножества двоичной строки?

Question

У меня проблема, я не знаю, как ее решить.

У меня есть двоичная строка, и я хочу сгенерировать все возможные двоичные подстроки.

Пример:

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

Как я могу сделать это, быстро и умно?

Answer 1

Магия - предполагает битовую маску:

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

Вы можете использовать ту же логику, хотя она немного сложнее, с двоичной строкой.

Answer 2

Неважно - черт, я забыл, что он у тебя в строке, а не в int / long / что угодно. Вы все еще можете использовать ту же логику, хотя ... Просто посчитайте в двоичном коде, но используйте только те позиции, которые содержат 1.

Просто мысли вслух.

Давайте возьмем строку 1001

То, что вы хотите, я думаю, это четыре числа 1001, 1000, 0001 и 0000, верно?

Если это так, то вы подсчитываете «одни» позиции.

Один из способов сохранить исходный номер

orig = n;

, а затем начинайте итерацию по этому и каждому нижнему числу

while(n--)

но каждую итерацию игнорируйте те, которые пытаются поставить 1 в позицию 0:

    if(n & !orig)
        continue;

Если вы ожидаете, что оно будет разреженным - как во многих нулях с очень небольшим числом единиц, вы можете использовать механизм сдвига. Допустим, ваш номер 1000 1001

Обратите внимание, есть три 1, верно? Так что просто посчитай от 000 до 111

Но для каждой итерации распределите биты снова:

n & 0000 0001 | n << 2 & 0000 1000 | n << 5 & 1000 0000 </p>

или другой способ думать об этом:

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

Это может быть медленнее, чем другое решение, в зависимости от того, сколько единиц появляется, хотя оно включает внутренний цикл с 1 итерацией для каждой 1 в исходном числе.

Извините за сдвиг между двоичным и десятичным - я могу сделать все это в шестнадцатеричном виде, если хотите:)

Сейчас я не могу придумать шаблон, который напрямую отображает биты без смещения - это будет работать лучше всего.

Answer 3

Это делает это:

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

Алгоритм делает это:

1. Начните с вектора, содержащего только пустую битовую строку '00000 ...'
2. Для каждого 1 во входной строке: создать копию каждой строки в выходном векторе с этим набором 1.

Я думаю, что это в значительной степени оптимально.

Answer 4

Использовать рекурсию

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 5

1. Если вы просто хотите, чтобы значения были ниже числового значения двоичной строки, продолжайте убирать одно из двоичной строки, пока не доберетесь до 0.
2. Если вы хотите, чтобы все значения, которые могут быть представлены этим числом двоичных цифр, вычитайте 1 из наибольшего числа, которое может быть представлено этим количеством цифр, пока не получите 0.

Этот вопрос появляется на сайтах Katcha с кодом