Lesson 7

For a set of size \(n\), there’s a natural bijection (that is, one-to-one correspondence) between its subsets and all binary sequences of length \(n\) (which are also known in programming as masks). The easiest way to explain this is with an example. Consider the set \(\{a,b,c\}\) of size \(n=3\). Then each bit of a binary sequence of length \(n=3\) corresponds to an element of the set: if the bit is zero, we don’t take the element, and if it’s one—we do take it.

This correspondence helps turn the generation of binary sequences into generation of all subsets. In the code below, we gradually increase the variable \(\texttt{index}\) and either take the current element \(\texttt{universe[index]}\), or skip it.

def subsets(universe):
    def helper(subset, index):
        if index == len(universe):
            yield subset
        else:
            yield from helper(subset, index + 1)
            yield from helper(subset + [universe[index]], index + 1)

    yield from helper(subset=[], index=0)


for item in subsets([5, 3, 7, 4]):
    print(item, sep='', end=' ')

[] [4] [7] [7, 4] [3] [3, 4] [3, 7] [3, 7, 4] [5] [5, 4] [5, 7] [5, 7, 4] [5, 3] [5, 3, 4] [5, 3, 7] [5, 3, 7, 4]