随机生成固定和的位串

Question

我想生成一组随机生成的长度为 N 的位串，但我想确保每个位串的总和等于某个数，比如 $k$。我将如何在 Python 中执行此操作而不生成所有可能的位串并删除那些加起来不等于 k 的位串？

示例：假设我们要生成 10 个不同的位串，每个位串的长度为 96，但我们必须确保每个位串恰好有 60 个。我们怎样才能做到这一点？

谢谢

Answer 1

创建一个 k 个前导列表，然后是 N - k 个零，然后随机洗牌该列表。使用 bitstring，其实现可能如下所示：

import random

import bitstring


def make_rnd_bitstring(N: int, k: int) -> bitstring.BitArray:
    assert N >= k >= 0

    bits = ['1'] * k + ['0'] * (N - k)
    random.shuffle(bits)

    return bitstring.BitArray(bin="".join(bits))

您可以根据需要随机生成位串多次调用此函数。

Answer 2

如果具有适当位 set/unset 的整数就足够了，此代码将执行问题的要求：

(注意：已更新以消除不必要的列表列表)

import random
bitstrings, toShuffle = [], [1]*60 + [0]*(96-60)
for _ in range(10):
    bitstring, L = 0, random.sample(toShuffle, len(toShuffle))
    for bit in L:
        bitstring = (bitstring << 1) | bit
    bitstrings.append(bitstring)
[print(f"{b:>100b}") for b in bitstrings]

示例输出：

    111110101111011101010101111010010100011011100111101000010101001111110001111011111111011001010101
    111101111011011111101111011011011101011010111110111100111101011000010001100101011000001001001111
    111000101100101111111111100001011001111110010101011111110110101011001111100101101011111101100000
     10101111011001010110111011111110101101001111100100000110101111100111111101111001110100001111010
    101110100010101110111100101011101101001010100111011011010110100110110011011110110111111010110111
    110101010111011101110111010011011010110110100110000110001001110101101101101101111111011110111001
      1111101101100111011111100011000100101001111011010011000111110010011011001111101011111111010111
    110111101111101011011011001010111110111111110011100100001110010101001100111101011010001100111110
     11011011011101001001111111100011000011010111011101111110010101101110011001110101110011110110101
    110001001010001111010111011001011011011011111011000010110001111011101111100111011011101110111101

更新#2：纯属娱乐...

这里有一个 one-liner 来做同样的事情：

import random
def generateBitStrings(nStrings, n, k):
    return [(([bitstring:=0] + [(bitstring := (bitstring << 1) | bit) for bit in random.sample([1]*k + [0]*(n - k), n)])[-1]) for _ in range(nStrings)]
[print(f"{b:>100b}") for b in generateBitStrings(10, 96, 60)]

随机生成固定和的位串

Randomly Generate bitstrings with fixed sum

python

bit-manipulation

bitstring