Randomly Generate bitstrings with fixed sum

Question

I would like to generate a set of randomly generated bit strings with a certain length N, but I would like to ensure that the sum of each bit string adds up to a certain number, say $k$. How would I go about doing this in Python without generating all possible bit strings and removing ones that don't add up to k?

Example: say we would like to generate 10 different bit strings, each with length 96, but we must ensure that each bit string has exactly 60 ones. How can we achieve this?

Thanks

Answer 1

Create a list of k leading ones, followed by N - k zeros, and then randomly shuffle that list. Using bitstring, an implementation of this could look like the following:

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))

You can call this function as many times as you need randomly generated bit strings.

Answer 2

If integers with the appropriate bits set/unset will suffice, this code will do what the question asks:

(NOTE: Updated to eliminate unnecessary list of lists)

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]

Sample output:

    111110101111011101010101111010010100011011100111101000010101001111110001111011111111011001010101
    111101111011011111101111011011011101011010111110111100111101011000010001100101011000001001001111
    111000101100101111111111100001011001111110010101011111110110101011001111100101101011111101100000
     10101111011001010110111011111110101101001111100100000110101111100111111101111001110100001111010
    101110100010101110111100101011101101001010100111011011010110100110110011011110110111111010110111
    110101010111011101110111010011011010110110100110000110001001110101101101101101111111011110111001
      1111101101100111011111100011000100101001111011010011000111110010011011001111101011111111010111
    110111101111101011011011001010111110111111110011100100001110010101001100111101011010001100111110
     11011011011101001001111111100011000011010111011101111110010101101110011001110101110011110110101
    110001001010001111010111011001011011011011111011000010110001111011101111100111011011101110111101

UPDATE #2: just for fun ...

Here's a one-liner to do the same thing:

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)]