lesson 80 Collections & Itertools · intermediate

Every pair, once: combinations

`itertools.combinations(items, 2)` gives every pair from a list exactly once, never an item with itself and never the same pair twice. It replaces a nested loop that is easy to get wrong.

You'll be able to

Produce every pair, or every group of r items, with combinations(items, r)
Know how many there are, n × (n − 1) / 2 pairs, and that the number grows fast
Sort items first when the same pair can arrive in either order

The idea

A league where every team plays every other team once; a check that no two meetings overlap; finding which tags are asked about together: each needs every pair from one list.

With loops you would write a loop inside a loop and make sure the inner one starts after the outer item, or you get an item paired with itself and every pair twice. from itertools import combinations does it for you: combinations(items, 2) yields each pair as a tuple, in the order of the list, each pair once. combinations(items, 3) gives every group of three. For n items there are n × (n − 1) / 2 pairs: 6 for 4 teams, but 499,500 for 1,000 items.

Run each example to see what it prints. Running examples doesn't count toward progress.

example-1.py · Fixtures for a four-team league

from itertools import combinations

teams = ["Harbor FC", "Rovers", "City", "Athletic"]
fixtures = list(combinations(teams, 2))
print(len(fixtures))
for home, away in fixtures:
    print(home, "v", away)

example-2.py · Forgetting the group size

from itertools import combinations

teams = ["Harbor FC", "Rovers", "City"]
print(list(combinations(teams)))

Pairs combine well with Counter. To find the tags most often asked about together, count every pair of tags on every question. A question tagged pandas, python and another tagged python, pandas are about the same pair, so sort each tag list first: then the pair always comes out in the same order.

example-3.py · Tags asked about together

from collections import Counter
from itertools import combinations

def tag_pairs(questions, n):
    pairs = Counter()
    for question in questions:
        for pair in combinations(sorted(question["tags"]), 2):
            pairs[pair] += 1
    return pairs.most_common(n)

questions = [
    {"tags": ["python", "pandas"]},
    {"tags": ["pandas", "python", "datetime"]},
    {"tags": ["python", "datetime"]},
    {"tags": ["python", "list"]},
]
print(tag_pairs(questions, 2))

When to use it: round-robin schedules, comparing every record with every other (overlaps, possible duplicates, distances), and co-occurrence counts. Mistakes to avoid: forgetting r; counting the same pair twice because the items arrived in different orders (sort first); and running it over a huge list without thinking: 10,000 records make almost 50 million pairs. When a shared key can find the matches (same email), grouping by that key is far faster; pairs are for tests that compare two records.

Review

combinations(items, r) yields every group of r items once, in list order, never repeating an item.
n items make n × (n − 1) / 2 pairs; that grows fast, so use pairs for tests that really compare two records.
Sort items first when a pair can arrive in either order.
Next module: nested data, reading values deep inside lists of dictionaries with missing keys.

Practise this