Using itertools.combinations_with_replacement in Python
python itertools combinations_with_replacement: Learn how to use itertools.combinations_with_replacement to generate multisets, with practical examples, performance no...
When you need to generate all multisets of a fixed size from an iterable, python itertools combinations_with_replacement is the tool that does exactly that. This function from the itertools module returns all possible tuples of length r where elements can repeat, and the order of elements in each tuple is non-decreasing according to the input order. It is the right choice when the selection order does not matter and repetition is allowed, such as counting coin combinations or generating all possible 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 sorted according to the original order of the input, and duplicates are allowed. This is equivalent to generating all multisets of size r from the input set. The number of results is given by the binomial coefficient C(n + r - 1, r), where n is the number of distinct elements in the input. 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.
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 exponential 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 sums 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 4.2 trillion, making it impossible 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. The function is implemented in C, making it faster than a pure-Python equivalent, 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.