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

Question

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

0111
1011
1101
1110

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

Answer 1

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

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

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

Рекурсивный вызов глубины 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 2

Один возможный 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 - число 1 с в "0111".

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