Lesson 5

Although there are standard methods to enumerate binary sequences, it’s important to be able to implement such enumeration manually: this is useful when developing efficient algorithms.

The sequences of length \(n=4\) generated above suggest the following method: the first half of the strings starts with zero, and the second with one. Thus, to enumerate all binary sequences of length \(n\), take all binary sequences of length \(n-1\) and prepend \(0\) to them, then take the same ones and prepend \(1\) to them. (By the way, you can append instead of prepend. Then you’ll still enumerate all binary strings of length \(n\), just in a different order.)

def binary_strings(n):
    if n > 0:
        yield from (head + tail for head in '01' for tail in binary_strings(n - 1))
    else:
        yield ''

print(*binary_strings(4))

0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111