Using itertools.combinations_with_replacement in Python
Learn how to use itertools.combinations_with_replacement in Python to generate multisets, with syntax, practical examples, and performance considerations.
itertools.combinations_with_replacement generates all multisets of a fixed size from an iterable: it returns tuples of length r in which elements may repeat and the output order is non-decreasing according to the input order. Use it when selection order does not matter and repetition is allowed, such as counting coin-change options or enumerating indistinguishable dice rolls.
How combinations_with_replacement Works
The function produces tuples in lexicographic order based on the input iterable. For each tuple, the elements are arranged according to the original order of the input, and duplicates are allowed. When the input values are distinct, this is equivalent to generating all multisets of size r from the input. The number of results is given by the binomial coefficient C(n + r - 1, r), where n is the number of elements in the input (the length of the tuple created internally). For example, with n = 3 and r = 2, there are C(4, 2) = 6 tuples.
from itertools import combinations_with_replacement list(combinations_with_replacement('ABC', 2)) # [('A', 'A'), ('A', 'B'), ('A', 'C'), ('B', 'B'), ('B', 'C'), ('C', 'C')]
The output shows that each tuple is sorted, and repeated elements are allowed. The order of the input iterable determines the sort order; if the input is not sorted, the output will reflect that order. If the input contains duplicate values, positions are still treated as distinct, so duplicate tuples can appear and the count formula above uses the number of elements rather than the number of unique values.
Basic Syntax and Parameters
The signature is combinations_with_replacement(iterable, r). The iterable can be any iterable, but it is converted to a tuple internally to allow repeated iteration. The r parameter must be a non-negative integer. If r is zero, the function yields a single empty tuple, regardless of the iterable's content. If the iterable is empty and r is greater than zero, no results are produced.
list(combinations_with_replacement([], 2)) # [] list(combinations_with_replacement([1, 2], 0)) # [()]
The function returns an iterator, not a list. This is important for memory efficiency when r or n is large. You can iterate over it directly or convert it to a list if you need all results at once, but be aware of the combinatorial growth in the number of results.
Practical Examples: Counting and Partitioning
A common use case is counting the number of ways to make change for a given amount using a set of coin denominations, where the order of coins does not matter and each coin can be used multiple times. For example, to find all combinations of coins (1, 2, 5) that sum to 5:
from itertools import combinations_with_replacement coins = [1, 2, 5] target = 5 ways = [combo for r in range(1, target // min(coins) + 1) for combo in combinations_with_replacement(coins, r) if sum(combo) == target] # ways = [(5,), (1, 2, 2), (1, 1, 1, 2), (1, 1, 1, 1, 1)]
Another example is generating all possible unordered outcomes when rolling two six-sided dice, where the dice are indistinguishable:
from itertools import combinations_with_replacement outcomes = list(combinations_with_replacement(range(1, 7), 2)) # [(1, 1), (1, 2), (1, 3), (1, 4), (1, 5), (1, 6), # (2, 2), (2, 3), (2, 4), (2, 5), (2, 6), # (3, 3), (3, 4), (3, 5), (3, 6), # (4, 4), (4, 5), (4, 6), # (5, 5), (5, 6), # (6, 6)]
These examples illustrate how the function naturally handles repetition without needing to filter out duplicates from a product or combinations result.
combinations_with_replacement vs combinations vs product
The choice between these three functions depends on whether order matters and whether repetition is allowed. The following table summarizes the key differences:
| Function | Order matters | Repetition allowed | Example with 'AB' and r=2 |
|---|---|---|---|
product | Yes | Yes | ('A','A'), ('A','B'), ('B','A'), ('B','B') |
combinations | No | No | ('A','B') |
combinations_with_replacement | No | Yes | ('A','A'), ('A','B'), ('B','B') |
Use product when the sequence order matters, such as generating all possible passwords. Use combinations when each element can appear only once and order is irrelevant, such as selecting a committee from a set of people. Use combinations_with_replacement when repetition is allowed and order does not matter, such as selecting ice cream scoops from a set of flavors.
Performance and Memory Considerations
The function returns a lazy iterator, so it does not precompute all tuples in memory. Each tuple is generated on demand, and the memory footprint is proportional to r for each yielded tuple, plus a small constant for the internal state. This is a significant advantage over building a list of all combinations manually, which would require storing C(n + r - 1, r) tuples.
However, the number of results grows combinatorially. For n = 10 and r = 10, there are C(19, 10) = 92378 tuples, which is manageable. But for n = 100 and r = 10, the count exceeds 40 trillion, making it impractical to iterate over all results in reasonable time. Always estimate the output size before using this function in a loop that might not terminate.
If you only need to count the number of combinations without generating them, use the mathematical formula directly instead of iterating. The math.comb function can compute C(n + r - 1, r) efficiently.
Common Pitfalls and Edge Cases
One subtle issue is that the input iterable is consumed and converted to a tuple. If you pass an iterator that is already partially consumed, the results will reflect only the remaining elements. For example:
gen = (x for x in range(5)) next(gen) # consume 0 list(combinations_with_replacement(gen, 2)) # uses 1,2,3,4 only
Another edge case is when r is larger than the number of elements. Unlike combinations, which returns no results when r > n, combinations_with_replacement still produces results because repetition is allowed. For instance, with n = 2 and r = 3, you get C(4, 3) = 4 tuples.
If the input contains duplicate elements, the function treats them as distinct positions. This means that duplicate values in the input will produce duplicate tuples in the output. If you need unique multisets, deduplicate the input first with set() or dict.fromkeys().
When to Use combinations_with_replacement in Production Code
In production, this function is useful for generating test cases, enumerating state spaces, or implementing algorithms that require multiset combinations. For example, in a pricing engine, you might need to generate all possible bundles of products where a product can appear multiple times. The lazy iterator allows you to process each combination as it is generated, which is ideal for streaming or early termination when a condition is met.
One important decision criterion is whether you need to process all combinations or just a subset. If you need to find a combination that satisfies a predicate, you can break out of the loop as soon as you find it, saving significant time. The iterator does not need to be fully consumed.
Another consideration is compatibility. combinations_with_replacement has been available since Python 3.1, so it is safe to use in any modern Python codebase. In CPython, the function is implemented in C, but the algorithmic complexity remains the same.
When performance is critical, avoid converting the iterator to a list unless you know the result count is small. Instead, iterate directly and process each tuple as it arrives. This keeps memory usage flat and allows the garbage collector to reclaim each tuple after it is no longer referenced.
Finally, if you find yourself filtering the output of product to remove order-sensitive duplicates, combinations_with_replacement is almost always the more efficient and clearer choice. It expresses the intent directly and avoids generating many unnecessary tuples.