Сгенерируйте все двоичные строки длиной 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#Следующее изменение

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

Предположим, у нас есть шаблон из 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

Питон

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 k битов из n общего количества битов.itertools - хороший модуль, который делает это за нас.itertools.комбинации (диапазон (n), k) будут выбирать k битов из [0, 1, 2 ...n-1] и тогда это просто вопрос построения строки с учетом этих битовых индексов.

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

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

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

Answer 3

Забудьте о реализации ("будь это сделано с помощью строк", очевидно, является реализация проблема!) - подумайте о алгоритм, ради всего святого...прямо как в твоем самом первом теге, чувак!

То, что вы ищете, - это все комбинации из 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)

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

Функциональные языки, соответствующие шаблону, такие как SML или Haskell, могут быть лучшими для выражения этого псевдокода (процедурные языки, такие как my big love Python, на самом деле могут слишком глубоко маскировать проблему, включая слишком богатую функциональность, такую как itertools.combinations, который делает всю тяжелую работу за вас и поэтому СКРЫВАЕТ это от вас!).

С чем вы больше всего знакомы для этой цели - Scheme, SML, Haskell, ...?Я буду рад перевести приведенный выше псевдокод для вас.Конечно, я могу сделать это и на таких языках, как Python, но поскольку суть в том, чтобы заставить вас понять механику выполнения этого домашнего задания, я не буду использовать слишком богатую функциональность, такую как itertools.combinations, а скорее рекурсия (и исключение рекурсии, если необходимо) на более очевидных примитивах (таких как head, tail и конкатенация).Но, пожалуйста, дайте нам знать, с каким псевдокодоподобным языком вы больше всего знакомы!(Вы понимаете, что проблема, которую вы излагаете, одинаково эквивалентна "вывести все комбинации из K элементов или диапазона (N)", верно?).

Answer 4

Этот метод 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 5

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

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

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

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

Answer 6

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

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 7

В более общем виде приведенная ниже функция предоставит вам все возможные комбинации индексов для задачи N choose 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

Один из возможных 1,5-лайнеров:

$ python -c 'import itertools; \
             print set([ n for n in itertools.permutations("0111", 4)])'

set([('1', '1', '1', '0'), ('0', '1', '1', '1'), ..., ('1', '0', '1', '1')])

..где k является числом 1s в "0111".

Модуль itertools объясняет эквиваленты для своих методов;смотрите эквивалент для способ перестановки.

Answer 9

Я бы попробовал рекурсию.

Существует n цифр, k из которых состоят из 1s.Другой способ просмотреть это - последовательность из k + 1 слотов с распределенными между ними n-k 0s.То есть (запуск из 0 секунд, за которым следует 1) k раз, затем следует еще один запуск из 0 секунд.Любой из этих прогонов может иметь нулевую длину, но общая длина должна быть n-k.

Представьте это в виде массива из k + 1 целых чисел.Преобразуйте в строку в нижней части рекурсии.

Рекурсивный вызов depth n-k, метода, который увеличивает один элемент массива перед рекурсивным вызовом, а затем уменьшает его в k + 1 раз.

На глубине n-k выведите строку.

int[] run = new int[k+1];

void recur(int depth) {
    if(depth == 0){
        output();
        return;
    }

    for(int i = 0; i < k + 1; ++i){
        ++run[i];
        recur(depth - 1);
        --run[i];
    }

public static void main(string[] arrrgghhs) {
    recur(n - k);
}

Прошло некоторое время с тех пор, как я работал на Java, так что, вероятно, в этом коде есть некоторые ошибки, но идея должна сработать.

Answer 10

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

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

Я бы опубликовал этот комментарий к первоначальному вопросу, но моя карма недостаточно высока.Извините.

Answer 11

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

Используя python's 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 12

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

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

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)