Каков эффективный код для генерации n двоичных чисел с k битами, установленными в единицу?

Question

Есть ли эффективный код для генерации чисел с n цифрами в их двоичном представлении с точно r битами, установленными как один?

Также это хорошая стратегия для создания масок для нахождения NcR комбинаций набора?

Я думал о генерации всех 2^n чисел и подсчете их битов, но подсчет бит кажется O(nlogn).

Answer 1

Что ж, если нам дано число с установленными K битами, как мы можем найти следующее наибольшее число с установленными K битами? Если мы делаем это неоднократно, мы можем генерировать их все.

Генерация следующего разбивается на пару простых правил:

1. Старший бит, который изменяется, должен измениться с 0 на 1. В противном случае новое число будет меньше заданного.
2. Старший бит, который изменяется, должен быть самым низким из возможных. В противном случае между текущим и новым будет другое действительное число. Когда мы меняем бит с 0 на 1, мы должны менять другой бит с 1 на 0, и этот бит должен быть меньше, поэтому старший бит, который мы хотим изменить с 0 на 1, является младшим 0 битом с 1 битом в более низкой позиции.
3. Остальные младшие биты должны быть установлены в их наименьшую действительную конфигурацию. В противном случае между текущим и новым снова будут другие действительные числа. Наименьшая допустимая конфигурация для младших битов - та, в которой все 1 бит находятся в самых низких позициях.

Оказывается, есть небольшие бинарные математические приемы, которые легко реализуют все эти правила. Вот это в Python:

N = 6 # length of numbers to generate
K = 4 # number of bits to be set

cur = (1<<K)-1  #smallest number witk K bits set

while cur < (1<<N):

    print format(cur,'b')

    #when you subtract 1, you turn off the lowest 1 bit
    #and set lower bits to 1, so we can get the samallest 1 bit like this:
    lowbit = cur&~(cur-1)

    #when you add lowbit, you turn it off, along with all the adjacent 1s
    #This is one more than the number we have to move into lower positions
    ones = cur&~(cur+lowbit)

    #cur+lowbit also turns on the first bit after those ones, which
    #is the one we want to turn on, so the only thing left after that
    #is turning on the ones at the lowest positions
    cur = cur+lowbit+(ones/lowbit/2)

Вы можете попробовать это здесь: https://ideone.com/ieWaUW

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