Home/Learn/Python A–Z/itertools & functools — lru_cache, product, groupby & reduce

itertools & functools — lru_cache, product, groupby & reduce

Advanced

Stdlib Power Tools

@lru_cache memoizes recursion in one decorator line; itertools generates combinations, permutations and products lazily — brute-force search and DP speedups for free.

Overview

functools.lru_cache turns exponential recursive solutions into memoized ones with a single decorator — the fastest way to a working DP solution in interviews (say "I'd memoize with lru_cache, here's the recurrence"). itertools supplies lazy combinatorics: permutations, combinations, product replace hand-written backtracking for brute-force phases; chain, groupby, accumulate handle sequence plumbing. Together they are the "I write Python like a professional" modules.

@lru_cache — Memoization in One Line

Arguments become the cache key (must be hashable). maxsize=None means unbounded. fib goes from O(2^n) to O(n) with zero manual bookkeeping.

lru_cache: recursion → DP with a decorator

from functools import lru_cache

@lru_cache(maxsize=None)          # or @cache in 3.9+
def fib(n):
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

print(fib(100))                    # instant — 354224848179261915075
print(fib.cache_info())            # hits=98 misses=101 ...

# Classic DP: climbing stairs / ways to reach n
@lru_cache(maxsize=None)
def ways(n):
    if n <= 1:
        return 1
    return ways(n - 1) + ways(n - 2)

# functools.partial — pre-fill arguments
from functools import partial
def power(base, exp): return base ** exp
square = partial(power, exp=2)
print(square(9))                   # 81

# functools.reduce — fold a sequence (use sparingly)
from functools import reduce
print(reduce(lambda a, b: a * b, [1, 2, 3, 4]))   # 24

itertools — Lazy Combinatorics & Sequence Tools

combinations (order-less), permutations (ordered), product (cross join / nested loops). All lazy. groupby groups CONSECUTIVE equal items — sort first for full grouping.

Brute force + prefix sums without hand-rolled loops

from itertools import (combinations, permutations, product,
                       chain, groupby, accumulate, islice)

team = ["asha", "ravi", "neha"]
print(list(combinations(team, 2)))
# [('asha','ravi'), ('asha','neha'), ('ravi','neha')]
print(len(list(permutations(team))))     # 6 orderings

# product = nested loops, flattened
for size, color in product(["S", "M"], ["red", "blue"]):
    pass                                  # 4 combos

# All subsets (power set) — brute-force enumerator
nums = [1, 2, 3]
subsets = chain.from_iterable(combinations(nums, r) for r in range(len(nums)+1))
print(list(subsets))   # () (1,) (2,) (3,) (1,2) ... (1,2,3)

# accumulate — running totals (prefix sums!)
print(list(accumulate([3, 1, 4, 1, 5])))  # [3, 4, 8, 9, 14]

# groupby — consecutive runs (run-length encoding)
s = "aaabbc"
print([(ch, len(list(g))) for ch, g in groupby(s)])
# [('a', 3), ('b', 2), ('c', 1)]

Key Points to Remember

1@lru_cache memoizes by arguments (hashable only) — instant DP from recursion
2combinations = unordered picks, permutations = ordered, product = nested loops
3accumulate gives prefix sums; groupby groups CONSECUTIVE items (sort first!)
4Everything in itertools is lazy — islice to take a finite window

Interview Questions

How does lru_cache work and what must be true about the function's arguments?

MediumGoogle

Generate all subsets of a list using itertools.

MediumMicrosoft

What surprising behaviour does groupby have on unsorted data?

HardThoughtworks

Ask Aria about itertools & functools — lru_cache, product, groupby & reduce

Your personal AI tutor — ask anything about this concept

Revision Status

Personal Notes

Discussion

Loading discussion…

collections — Counter, defaultdict & deque

datetime — Dates, Timezones & Durations