Itertools¶

Tuples, lists, sets, and dictionaries are iterables, meaning a for loop can step through them, one element at a time. The built-in itertools module provides tools for looping over one or more iterables in specialized ways. We conclude this lab by highlighting and demonstrating a few of these tools.

import itertools

Infinite Iterators¶

Function	Description
`cycle(iterable)`	If `iterable` is nonempty, yield its items repeatedly, looping back to the start forever.
`count(start, step)`	Yield `start`, `start + step`, `start + 2*step`, forever.
`repeat(item)`	Yield `item` over and over forever.

colors = ["red", "green", "blue"]

# Cycle through a list of colors indefinitely.
count = 0
for color in itertools.cycle(colors):
    if count >= 7:
        break
    print(color, end=" ")
    count += 1

red green blue red green blue red

Cycle on and on and on

Like a while True: loop, a for loop over itertools.cycle() with a nonempty input has no natural end and must be paired with something that stops it, such as a break statement.

Joined Iterators¶

Function	Description
`accumulate(x)`	Yield `x[0]`, then `x[0] + x[1]`, then `x[0] + x[1] + x[2]`, and so on.
`chain(A, B)`	Yield items of `A`, then of `B`, as if they were a single sequence.
`pairwise(x)`	Yield pairs of consecutive items: `(x[0], x[1])`, then `(x[1], x[2])`, and so on.

values = [5, 3, 7, 6, 9, 3, 7, 5, 6, 1, 2, 3, 1, 3, 2]

# Find the average of every pair of neighboring items.
print([(a + b) / 2 for (a, b) in itertools.pairwise(values)])

[4.0, 5.0, 6.5, 7.5, 6.0, 5.0, 6.0, 5.5, 3.5, 1.5, 2.5, 2.0, 2.0, 2.5]

Combinatoric Iterators¶

Function	Description
`product(A, B)`	Yield elements of the Cartesian product \(A \times B\).
`combinations(A, r)`	Yield every `r`-element combination from `A` with order ignored.
`permutations(A, r)`	Yield every `r`-element tuple of `A` with order mattering.
`combinations_with_replacement(A, r)`	Yield every `r`-element combination from `A` with repeats allowed and order ignored.

These functions treat items in different input positions as distinct, even when their values are equal.

Products¶

Given two sets \(A\) and \(B\), their Cartesian product \(A \times B\) is the set of ordered pairs whose first element is from \(A\) and whose second element is from \(B\):

\[ A \times B = \{(a, b) : a\in A,~b\in B\}. \]

If \(|A| = n\) and \(|B| = m\), then \(|A\times B| = nm\): the size of the Cartesian product is the product of the sizes.

sizes = ["S", "M", "L"]
colors = ["red", "blue"]

print(list(itertools.product(sizes, colors)))

[('S', 'red'), ('S', 'blue'), ('M', 'red'), ('M', 'blue'), ('L', 'red'), ('L', 'blue')]

# List elements of the Cartesian product A x A x A where A = {"X", "Y"}.
print(list(itertools.product("XY", repeat=3)))

[('X', 'X', 'X'), ('X', 'X', 'Y'), ('X', 'Y', 'X'), ('X', 'Y', 'Y'), ('Y', 'X', 'X'), ('Y', 'X', 'Y'), ('Y', 'Y', 'X'), ('Y', 'Y', 'Y')]

Combinations¶

A \(k\)-combination of a collection is a set of \(k\) distinct items chosen from it, where the order of those items does not matter. If a collection has \(n\) distinct elements, then the number of possible combinations is given by

\[ \binom{n}{k} = \frac{n!}{k!(n - k)!} \]

where \(n! = n(n-1)(n-2)\cdots 3\cdot 2\cdot 1\) is the factorial. The number \(\binom{n}{k}\) is read “\(n\) choose \(k\)”.

Where itertools.product() chooses one item from each of several collections, itertools.combinations() chooses several items from a single collection.

for combo in itertools.combinations(["apple", "banana", "cherry", "date"], 2):
    print(combo)

('apple', 'banana')
('apple', 'cherry')
('apple', 'date')
('banana', 'cherry')
('banana', 'date')
('cherry', 'date')

# Find all pairs of these values that add to 7.
values = [1, 2, 3, 4, 5, 6]
print([pair for pair in itertools.combinations(values, 2) if sum(pair) == 7])

[(1, 6), (2, 5), (3, 4)]

Note that (1, 6) appears but (6, 1) does not, since itertools.combinations() treats a pair as unordered and produces each one exactly once.

Permutations¶

A \(k\)-permutation is similar to a \(k\)-combination, except that order matters: choosing \(x\) then \(y\) counts separately from choosing \(y\) then \(x\). Because there are \(k!\) different ways to arrange a tuple of \(k\) elements, the number of possible \(k\)-permutations in a collection of \(n\) elements is

\[ \binom{n}{k}k! = \frac{n!}{(n - k)!} = n(n-1)(n-2)\cdots(n-k+2)(n-k+1). \]

for combo in itertools.permutations(["apple", "banana", "cherry", "date"], 2):
    print(combo)

('apple', 'banana')
('apple', 'cherry')
('apple', 'date')
('banana', 'apple')
('banana', 'cherry')
('banana', 'date')
('cherry', 'apple')
('cherry', 'banana')
('cherry', 'date')
('date', 'apple')
('date', 'banana')
('date', 'cherry')

Problem 7

Let \(S\) be a set. The power set of \(S\) is the new set \(\mathcal{P}(S)\) whose elements are all the subsets of \(S\). In other words, \(A\in \mathcal{P}(S)\) exactly when \(A\subseteq S\). The power set \(\mathcal{P}(S)\) includes the empty set and \(S\) itself. For example, if \(S = \{1, 2, 3\}\), then

\[ \mathcal{P}(S) = \{\emptyset, \{1\}, \{2\}, \{3\}, \{1, 2\}, \{1, 3\}, \{2, 3\}, \{1, 2, 3\}\}. \]

Write a function named power_set() that accepts a set \(S\) and returns the power set \(\mathcal{P}(S)\) as a list of sets (sets are not hashable, so we cannot have a set of sets in Python).

Hint: Are subsets most closely related to products, combinations, or permutations?

Test Cases

The subsets may be listed in a different order.

print(power_set(set()))
print(power_set({1, 2}))
print(power_set({1, 2, 3}))
print(len(power_set(set(range(4)))))

[set()]
[set(), {1}, {2}, {1, 2}]
[set(), {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}]
16