More Itertools Techniques
These functions embody algorithms that iterate over potentially large result sets
from small collections of input data. Some kinds of problems have exact solutions
based on exhaustively enumerating a potentially gigantic universe of permutations.
The functions make it simple to emit a large number of permutations; in some cases,
the simplicity isn't actually optimal.
Enumerating the Cartesian product
The term Cartesian product refers to the idea of enumerating all the possible
combinations of elements drawn from a number of sets.
Mathematically, we might say that the product of two sets, {}1, 2,3,...,13×{}C,D,H,S,
has 52 pairs as follows:
{(1, C), (1, D), (1, H), (1, S), (2, C), (2, D), (2, H), (2, S), ...,
(13, C), (13, D), (13, H), (13, S)}
We can produce the preceding results by executing the following commands:
list(product(range(1, 14), '♣♦♥♠'))
[(1, '♣'), (1, '♦'), (1, '♥'), (1, '♠'),(2, '♣'), (2, '♦'), (2, '♥'),
(2, '♠'),... (13, '♣'), (13, '♦'), (13, '♥'), (13, '♠')]
The calculation of a product can be extended to any number of iterable collections.
Using a large number of collections can lead to a very large result set.
Reducing a product
In relational database theory, a join between tables can be thought of as a filtered
product. A SQL SELECT statement that joins tables without a WHERE clause will
produce a Cartesian product of rows in the tables. This can be thought of as the
worst-case algorithm: a product without any filtering to pick the proper results.
We can use the join() function to join two tables, as shown in the following
commands:
def join(t1, t2, where):):
return filter(where, product(t1, t2)))))
All combinations of the two iterables, t1 and t2, are computed. The filter()
function will apply the given where function to pass or reject items that didn't fit the
given condition to match appropriate rows from each iterable. This will work when
the where function returns a simple Boolean.