AdvancedPython Programming · Lesson 25 of 30 · Updated ·
itertools and functools — Permutations, Combinations, groupby, reduce and partial
Many coding-test questions ask for "all pairs", "all orders", "running totals" or "group the records by…". You can write nested loops for these, but Python's standard library already has fast, tested tools for them. itertools works with iterators (sequences of values), and functools works with functions. Most itertools functions return lazy iterators, like the generators you saw earlier, so we wrap them in list() to print them.
1. Combinatorics: product, permutations, combinations
These three answer the classic counting questions from aptitude and DSA.
| Function | What it gives | Order matters? | Repeats an item? |
|---|---|---|---|
product(A, B) | every pair (a, b), like nested loops | yes | — |
permutations(items, r) | every arrangement of r items | yes | no |
combinations(items, r) | every selection of r items | no | no |
combinations_with_replacement(items, r) | selections that may repeat an item | no | yes |
from itertools import product, permutations, combinations
print(list(product("AB", [1, 2])))
print(list(permutations("ABC", 2)))
print(list(combinations("ABC", 2)))
[('A', 1), ('A', 2), ('B', 1), ('B', 2)]
[('A', 'B'), ('A', 'C'), ('B', 'A'), ('B', 'C'), ('C', 'A'), ('C', 'B')]
[('A', 'B'), ('A', 'C'), ('B', 'C')]
A practical use: choosing a team captain and vice-captain is a permutation (the roles differ). Choosing any 2 students for a project is a combination.
from itertools import permutations, combinations
from math import perm, comb
students = ["Asha", "Ravi", "Neha", "Imran", "Kiran"]
print(len(list(permutations(students, 2))), perm(5, 2))
print(len(list(combinations(students, 3))), comb(5, 3))
# all 3-digit PINs using only the digits 1, 2, 3 with no digit repeated
print(["".join(p) for p in permutations("123")])
20 20
10 10
['123', '132', '213', '231', '312', '321']
When you only need the count, use math.perm and math.comb; generating every item is wasteful. product also has a repeat argument: product("01", repeat=3) gives all 8 three-bit binary strings.
2. chain, islice, count and cycle
from itertools import chain, islice, count, cycle
morning = ["Maths", "Physics"]
evening = ["Lab", "Sports"]
print(list(chain(morning, evening))) # join iterables
print(list(islice(count(100, 5), 4))) # 100, 105, ... take 4
days = cycle(["Mon", "Tue", "Wed"]) # repeats forever
print([next(days) for _ in range(5)])
['Maths', 'Physics', 'Lab', 'Sports']
[100, 105, 110, 115]
['Mon', 'Tue', 'Wed', 'Mon', 'Tue']
count and cycle never end, so always limit them with islice, zip or a break. islice(it, start, stop, step) works like slicing, but for any iterator, including generators that have no len().
3. accumulate: running totals
from itertools import accumulate
import operator
daily_sales = [120, 80, 150, 60]
print(list(accumulate(daily_sales))) # running total
print(list(accumulate(daily_sales, max))) # best so far
print(list(accumulate([1, 2, 3, 4], operator.mul))) # running product
[120, 200, 350, 410]
[120, 120, 150, 150]
[1, 2, 6, 24]
The running total is exactly a prefix sum array, which DSA problems use to answer "sum from day i to day j" quickly.
4. groupby: group neighbouring items
groupby(items, key) puts consecutive items with the same key into one group. The word "consecutive" is the key point: sort by the same key first, otherwise equal keys that are far apart become separate groups.
from itertools import groupby
results = [("Asha", "CSE"), ("Ravi", "ECE"), ("Neha", "CSE"), ("Imran", "ECE")]
for branch, group in groupby(results, key=lambda r: r[1]):
print("unsorted:", branch, [name for name, _ in group])
results.sort(key=lambda r: r[1])
for branch, group in groupby(results, key=lambda r: r[1]):
print("sorted: ", branch, [name for name, _ in group])
unsorted: CSE ['Asha']
unsorted: ECE ['Ravi']
unsorted: CSE ['Neha']
unsorted: ECE ['Imran']
sorted: CSE ['Asha', 'Neha']
sorted: ECE ['Ravi', 'Imran']
A neat use is run-length encoding, a common interview question:
from itertools import groupby
text = "aaabccdddd"
print("".join(f"{ch}{len(list(g))}" for ch, g in groupby(text)))
a3b1c2d4
5. functools.reduce
reduce(function, items, start) combines all items into one value by applying the function step by step: first to the start and item 1, then to that result and item 2, and so on.
from functools import reduce
marks = [72, 85, 90, 64]
print(reduce(lambda total, m: total + m, marks, 0))
print(reduce(lambda a, b: a if a > b else b, marks))
from math import gcd
print(reduce(gcd, [48, 180, 300])) # GCD of many numbers
311
90
12
For sums and maximums, sum() and max() are clearer. Use reduce when there is no built-in, such as the GCD of a whole list.
6. functools.partial
partial(func, fixed arguments) makes a new function with some arguments already filled in.
from functools import partial
def price_with_tax(amount, rate):
return round(amount * (1 + rate / 100), 2)
gst_18 = partial(price_with_tax, rate=18)
gst_5 = partial(price_with_tax, rate=5)
print(gst_18(1000), gst_5(1000))
to_binary = partial(int, base=2)
print(to_binary("1011"))
1180.0 1050.0
11
7. cache, lru_cache and cmp_to_key
@functools.cache (Python 3.9+) and @functools.lru_cache(maxsize=n) remember a function's results. The first is unlimited; the second keeps only the n most recently used results. You saw them in the decorators lesson.
cmp_to_key converts an old-style comparison function (returns negative, zero or positive) into a key= for sorting. It solves problems where the order depends on two items together, like the "largest number" interview question.
from functools import cmp_to_key
def compare(a, b):
# put a before b if a+b makes a bigger number than b+a
if a + b > b + a:
return -1
if a + b < b + a:
return 1
return 0
nums = ["3", "30", "34", "5", "9"]
print("".join(sorted(nums, key=cmp_to_key(compare))))
9534330
Common mistakes
- Using
groupbywithout sorting by the same key first. - Forgetting that most itertools results are iterators: you can loop over them only once, and printing them shows
<itertools… object>. - Generating all permutations just to count them; use
math.perm/math.comb. - Using
count()orcycle()without a limit, creating an endless loop. - Mixing up permutations (order matters) and combinations (order does not).
Quick recap
product= nested loops;permutations= ordered arrangements;combinations= unordered selections.chainjoins,isliceslices any iterator,count/cycleare infinite.accumulategives running totals (prefix sums) or running max.groupbygroups consecutive equal keys: sort first.reducefolds a list into one value;partialpre-fills arguments.cache/lru_cachememoise;cmp_to_keysorts with a two-item comparison.