尽可能快地找到所有具有一定权重的二进制字符串

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，我们得到110101011。你知道吗

我的研究要求我解析n=56和k=7这样的值，这在我的设备上大约需要24小时。我还想尝试n=72和k=8，这（基于上一个结果的时间）可能需要365天。所以我想知道两件事：

1. 这是生成这些二进制字符串的最快（非内存）密集型方法吗？

2. 有没有可能让我的多个CPU核同时处理这个问题？我假设itertools是通过一个序列进行解析的。如果（比方说）我们有一个双核CPU，第一个核可以解析序列的前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

我将当前的数字存储在一个整数变量中，然后执行二进制位操作（&，^，|）来移动这些位。具有较小长度和权重的递归，可能只需几行代码即可完成。你知道吗

二进制位运算可能比字符串运算快得多，特别是在不需要打印每个数字的情况下。你知道吗

Answer 2

在https://graphics.stanford.edu/~seander/bithacks.html#NextBitPermutation有一种非常快速的方法来生成按字母顺序排列的下一位置换。因为它使用编译器内部函数，所以您可能必须用C编译它，然后使用Python的C接口来实际操作它。如果从k个最低有效位设置为1开始，其余位设置为0，则应该能够使用此操作在整个集合中进行置换。你知道吗

由于此操作（大部分）近似于迭代器，因此应该能够通过将问题分解为多个线程可以迭代的范围来并行化。你知道吗

要将整数转换回字符串，可以循环检查第一位（通过按位与1比较容易实现），如果是0，则将“0”前置到字符串，如果是1，则将“1”前置到字符串，然后进行右移。如果对位字符串的长度执行此操作，则已将整数转换为字符串。你知道吗

Answer 3

给定一个权重为k的值，您可以按如下方式获得词汇上的下一个值：

1. 在最右边的1的左边找到最右边的0。你知道吗
2. 将1从右边移到0中
3. 把所有其他的1移到0的右边，越远越好。你知道吗

这是Pandita算法的二进制版本：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语句中的二进制字符串。你知道吗