Найти все двоичные строки определенного веса максимально быстро

Question

Я хочу найти двоичные строки определенного веса.Количество таких строк увеличивается до точки ошибки памяти, поэтому в настоящее время я генерирую их с помощью генератора.Этот код генерирует всю длину n двоичных строк с весом k:

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

for b in kbits(length, weight):
    print(b)

Таким образом, для длины = 3 и веса = 2 мы получаем 110, 101, 011.

Мое исследование требует от меняпроанализируйте значения, такие как n = 56 и k = 7, что занимает около 24 часов на моем устройстве.Я также хотел бы попробовать n = 72 и k = 8, что (в зависимости от времени предыдущего результата) может занять 365 дней.Итак, мне интересно две вещи:

1. Является ли это самым быстрым (без памяти) интенсивным способом генерации этих двоичных строк?

2. Возможно ли иметь несколько ядер моего процессора, работающих на этом одновременно?Я предполагаю, что itertools анализирует последовательность.Если бы (скажем) у нас был двухъядерный процессор, было бы возможно, чтобы первое ядро ​​анализировало первые 50% последовательности, а второе - для второй половины?

РЕДАКТИРОВАТЬ:

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

for b in kbits(size, max_coclique):
    v = np.linalg.lstsq(N,np.array(list(b), dtype = float))

т.е.Мне требуется, чтобы конечный ожидаемый выходной формат для b был массивом numpy со значениями 0/1.(Это если не существует какого-либо чрезвычайно быстрого способа сделать все это - включая вычисление наименьших квадратов - другим способом.)

Примечание: я также запускаю это в Sage, так как используюсвою базу данных переходных групп.

Answer 1

Учитывая значение с весом k , вы можете получить следующее лексическое значение следующим образом:

1. Найти крайний правый 0 слева от крайнего правого 1.
2. переместить 1 справа в это 0
3. переместить все остальные 1 с правой стороны от этого нуля как можно дальше вправо.

Это двоичная версияАлгоритм Пандита: https://en.wikipedia.org/wiki/Permutation#Generation_in_lexicographic_order

Вы можете сделать это с помощью битовых манипуляций, например:

def kbits(n, k):
    limit=1<<n
    val=(1<<k)-1
    while val<limit:
        yield "{0:0{1}b}".format(val,n)
        minbit=val&-val #rightmost 1 bit
        fillbit = (val+minbit)&~val  #rightmost 0 to the left of that bit
        val = val+minbit | (fillbit//(minbit<<1))-1

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

Answer 2

Чрезвычайно быстрый метод для генерации лексографически следующей битовой перестановки доступен в https://graphics.stanford.edu/~seander/bithacks.html#NextBitPermutation.Поскольку он использует встроенные функции компилятора, вам, возможно, придется скомпилировать его в C, а затем использовать интерфейс C Python для его фактической работы.Если вы начнете с k младших значащих битов, установленных на 1, а остальных на 0, вы сможете использовать эту операцию для перестановки всего набора.

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

Чтобы преобразовать целые числа обратно в строку, вы можете выполнить цикл проверки первого бита (легко достигаетсявыполнение побитового И против 1) и добавление к строке «0», если это 0, или «1», если это 1, затем смещение вправо.Если вы сделаете это для длины строки битов, вы преобразуете целое число в строку.

Answer 3

Я бы сохранял текущее число в целочисленной переменной, а затем выполнял двоичные побитовые операции (&, ^, |) для перемещения битов.С рекурсией к меньшей длине и весу, что, вероятно, может быть сделано с несколькими строками кода.

Бинарные побитовые операции, вероятно, намного быстрее, чем строковые операции, особенно если вам не нужно печатать каждое число.