Lesson 9

Using standard generators in Python, you can enumerate subsets like this.

from itertools import product

u = [5, 3, 7, 4]

for seq in product(range(2), repeat=len(u)):
    print([u[i] for i in range(len(u)) if seq[i] == 1], 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]

In Python, it is also easy to enumerate all subsets of a fixed size:

from itertools import combinations

print(*combinations([5, 3, 7, 4], 2))

(5, 3) (5, 7) (5, 4) (3, 7) (3, 4) (7, 4)

from itertools import chain, combinations

u = [5, 3, 7, 4]
print(*chain.from_iterable(combinations(u, k) for k in range(len(u) + 1)))

() (5,) (3,) (7,) (4,) (5, 3) (5, 7) (5, 4) (3, 7) (3, 4) (7, 4) (5, 3, 7) (5, 3, 4) (5, 7, 4) (3, 7, 4) (5, 3, 7, 4)

Our manual method of enumerating subsets can be adapted to enumerate subsets of fixed size like this:

def combinations(universe, k):
    def helper(subset, index):
        if len(subset) == k:
            yield subset
        else:
            for last_index in range(index, len(universe)):
                yield from helper(subset + [universe[last_index]], last_index + 1)

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

print(*combinations([5, 3, 7, 4], 2))

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