pythonbit-manipulationbitstring

Randomly Generate bitstrings with fixed sum


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


Solution

  • 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.