Генерация всех двоичных строк длины n с установленным k битами

Question

Какой лучший алгоритм для поиска всех двоичных строк длины n, которые содержат набор k битов? Например, если n = 4 и k = 3, есть ...

0111
1011
1101
1110

Мне нужен хороший способ для генерации данных при любом n и любом k, поэтому я бы предпочел, чтобы это было сделано со строками.

Answer 1

Этот метод генерирует все целые числа с точно N '1' битами.

С https://graphics.stanford.edu/~seander/bithacks.html#NextBitPermutation

Вычислить лексикографически следующую битовую перестановку

Предположим, у нас есть набор из N битов, равный 1 в целом числе, и мы хотим следующая перестановка из N 1 бит в лексикографическом смысле. За Например, если N равно 3, а битовый шаблон равен 00010011, следующие шаблоны будет 00010101, 00010110, 00011001, 00011010, 00011100, 00100011, и так далее. Ниже приведен быстрый способ вычисления следующего перестановка.

unsigned int v; // current permutation of bits
unsigned int w; // next permutation of bits

unsigned int t = v | (v - 1); // t gets v's least significant 0 bits set to 1
// Next set to 1 the most significant bit to change,
// set to 0 the least significant ones, and add the necessary 1 bits.
w = (t + 1) | (((~t & -~t) - 1) >> (__builtin_ctz(v) + 1));

Встроенный компилятор __builtin_ctz(v) GNU C для процессоров x86 возвращает число конечных нулей. Если вы используете компиляторы Microsoft для x86, присуще _BitScanForward. Они оба испускают bsf инструкция, но эквиваленты могут быть доступны для других архитектур. Если нет, то рассмотрите возможность использования одного из методов подсчета последовательные нулевые биты, упомянутые ранее. Вот еще одна версия, которая имеет тенденцию быть медленнее из-за своего оператора деления, но это не требуется подсчет завершающих нулей.

unsigned int t = (v | (v - 1)) + 1;
w = t | ((((t & -t) / (v & -v)) >> 1) - 1);

Спасибо Дарио Снейдерманису из Аргентины, который предоставил это 28 ноября 2009 года.

Answer 2

Python

import itertools

def kbits(n, k):
    result = []
    for bits in itertools.combinations(range(n), k):
        s = ['0'] * n
        for bit in bits:
            s[bit] = '1'
        result.append(''.join(s))
    return result

print kbits(4, 3)

Output: ['1110', '1101', '1011', '0111']

Пояснение:

По сути, нам нужно выбрать позиции 1-бит. Существует n вариантов выбора k битов из n суммарных битов. itertools - хороший модуль, который делает это для нас. itertools.combination (range (n), k) выберет k бит из [0, 1, 2 ... n-1], а затем нужно просто построить строку с учетом этих битовых индексов.

Так как вы не используете Python, посмотрите псевдокод для itertools.combination здесь:

http://docs.python.org/library/itertools.html#itertools.combinations

Должно быть легко реализовано на любом языке.

Answer 3

Забудьте о реализации («быть сделано со строками», очевидно, является реализацией проблемы!) - подумайте об алгоритме , ради Пита ... так же, как и в твой самый первый TAG, чувак!

То, что вы ищете, это все комбинации из K элементов из набора N (индексы от 0 до N-1 из установленных битов). Это, очевидно, проще всего выразить рекурсивно, например, псевдокод:

combinations(K, setN):
  if k > length(setN): return "no combinations possible"
  if k == 0: return "empty combination"
  # combinations INcluding the first item:
  return (first-item-of setN) combined combinations(K-1, all-but-first-of setN)
   union combinations(K-1, all-but-first-of setN)

То есть, первый элемент либо присутствует, либо отсутствует: если он присутствует, у вас остается К-1 (из хвоста, или все, кроме елей), если отсутствует, все еще остается К, чтобы идти.

Функциональные языки сопоставления с образцом, такие как SML или Haskell, могут быть наилучшими для выражения этого псевдокода (процедурные, такие как мой Python большой любви, могут на самом деле замаскировать проблему слишком глубоко, включая слишком богатую функциональность, такую ​​как itertools.combinations, которая делает всю тяжелую работу за вас и поэтому скрывает это от вас!).

Что вам больше всего подходит для этой цели - Scheme, SML, Haskell, ...? Я буду рад перевести указанный выше псевдокод для вас. Конечно, я могу делать это и на таких языках, как Python, но поскольку дело в том, чтобы вы поняли механику этого домашнего задания, я не буду использовать слишком богатую функциональность, такую ​​как itertools.combinations, а скорее рекурсию ( и устранение рекурсии, если необходимо) для более очевидных примитивов (таких как голова, хвост и конкатенация). Но, пожалуйста, ДАЙТЕ нам знать, с каким псевдокодоподобным языком вы больше всего знакомы! (Вы ПОНИМАЕТЕ, что проблема, о которой вы говорите, идентична: «выведите все комбинации из K предметов или диапазона (N)», верно?).

Answer 4

Одна из проблем многих стандартных решений этой проблемы состоит в том, что генерируется весь набор строк, а затем итерируются, что может привести к исчерпанию стека. Это быстро становится громоздким для любых, кроме самых маленьких наборов. Кроме того, во многих случаях требуется только частичная выборка, но стандартные (рекурсивные) решения обычно разбивают проблему на части, которые сильно смещены в одном направлении (например, рассматривают все решения с нулевым начальным битом, а затем все решения с одним стартовым битом).

Во многих случаях было бы более желательно иметь возможность передавать битовую строку (с указанием выбора элемента) в функцию и возвращать следующую битовую строку таким образом, чтобы иметь минимальное изменение (это известно как серый код) и иметь представление всех элементов.

Дональд Кнут рассматривает целый ряд алгоритмов для этого в своей главе 3А, раздел 7.2.1.3: Генерация всех комбинаций.

Существует подход к решению итеративного алгоритма Грея для всех способов выбора k элементов из n при http://answers.yahoo.com/question/index?qid=20081208224633AA0gdMl со ссылкой на окончательный код PHP, указанный в комментарии (щелкните, чтобы развернуть его) внизу страницы.

Answer 5

Этот метод C # возвращает перечислитель, который создает все комбинации. Поскольку он создает комбинации по мере их перечисления, он использует только пространство стека, поэтому он не ограничен объемом памяти в количестве комбинаций, которые он может создать.

Это первая версия, которую я придумал. Длина стека ограничена длиной около 2700:

static IEnumerable<string> BinStrings(int length, int bits) {
  if (length == 1) {
    yield return bits.ToString();
  } else {
    if (length > bits) {
      foreach (string s in BinStrings(length - 1, bits)) {
        yield return "0" + s;
      }
    }
    if (bits > 0) {
      foreach (string s in BinStrings(length - 1, bits - 1)) {
        yield return "1" + s;
      }
    }
  }
}

Это вторая версия, которая использует двоичное разделение, а не разделение первого символа, поэтому оно использует стек намного эффективнее. Он ограничен только пространством памяти для строки, которую он создает в каждой итерации, и я протестировал его до длины 10000000:

static IEnumerable<string> BinStrings(int length, int bits) {
  if (length == 1) {
    yield return bits.ToString();
  } else {
    int first = length / 2;
    int last = length - first;
    int low = Math.Max(0, bits - last);
    int high = Math.Min(bits, first);
    for (int i = low; i <= high; i++) {
      foreach (string f in BinStrings(first, i)) {
        foreach (string l in BinStrings(last, bits - i)) {
          yield return f + l;
        }
      }
    }
  }
}

Answer 6

Python (функциональный стиль)

Используя python itertools.combinations, вы можете сгенерировать все варианты k наших n и отобразить эти варианты в двоичный массив с reduce

from itertools import combinations
from functools import reduce # not necessary in python 2.x

def k_bits_on(k,n):
       one_at = lambda v,i:v[:i]+[1]+v[i+1:]
       return [tuple(reduce(one_at,c,[0]*n)) for c in combinations(range(n),k)]

Пример использования:

In [4]: k_bits_on(2,5)
Out[4]:
[(0, 0, 0, 1, 1),
 (0, 0, 1, 0, 1),
 (0, 0, 1, 1, 0),
 (0, 1, 0, 0, 1),
 (0, 1, 0, 1, 0),
 (0, 1, 1, 0, 0),
 (1, 0, 0, 0, 1),
 (1, 0, 0, 1, 0),
 (1, 0, 1, 0, 0),
 (1, 1, 0, 0, 0)]

Answer 7

В более общем виде, приведенная ниже функция предоставит вам все возможные комбинации индексов для задачи выбора N K, которую затем можно применить к строке или к чему-либо еще:

def generate_index_combinations(n, k):

    possible_combinations = []

    def walk(current_index, indexes_so_far=None):
        indexes_so_far = indexes_so_far or []
        if len(indexes_so_far) == k:
            indexes_so_far = tuple(indexes_so_far)
            possible_combinations.append(indexes_so_far)
            return
        if current_index == n:
            return
        walk(current_index + 1, indexes_so_far + [current_index])
        walk(current_index + 1, indexes_so_far)

    if k == 0:
        return []
    walk(0)
    return possible_combinations

Answer 8

Один алгоритм, который должен работать:

generate-strings(prefix, len, numBits) -> String:
    if (len == 0):
        print prefix
        return
    if (len == numBits):
        print prefix + (len x "1")
    generate-strings(prefix + "0", len-1, numBits)
    generate-strings(prefix + "1", len-1, numBits)

Удачи!

Answer 9

Хорошо для этого вопроса (где вам нужно перебирать все подмаски в порядке возрастания их количества установленных бит), который был помечен как дубликат этого.

Мы можем просто перебрать все подмаски, добавить их в вектор и отсортировать по количеству установленных битов.

vector<int> v;
for(ll i=mask;i>0;i=(i-1)&mask)
    v.push_back(i);
auto cmp = [](const auto &a, const auto &b){
    return __builtin_popcountll(a) < __builtin_popcountll(b);
}
v.sort(v.begin(), v.end(), cmp);

Другим способом является итерация по всем подмаскам N раз и добавление числа к вектору, если число установленных битов равно i в i-й итерации.

Оба способа имеют сложность O (n * 2 ^ n)

Answer 10

Строки быстрее, чем массив целых чисел? Все решения, предшествующие строкам, вероятно, приводят к копированию строки на каждой итерации.

Так что, вероятно, наиболее эффективным способом был бы массив int или char, к которому вы добавляете. У Java есть эффективные растущие контейнеры, верно? Используйте это, если это быстрее чем строка. Или, если BigInteger эффективен, он, безусловно, компактен, поскольку каждый бит занимает всего один бит, а не целый байт или целое число. Но затем, чтобы перебрать биты, вам нужно «замаскировать бит» и переместить битовую маску в следующую позицию бит. Так что, вероятно, медленнее, если JIT-компиляторы не хороши в наши дни.

Я бы оставил комментарий к исходному вопросу, но моя карма недостаточно высока. К сожалению.