Why can itertools.combinations return duplicate tuples from one input list?

### Positional selection is the whole answer `itertools.combinations(iterable, r)` first turns its input into a tuple, then yields tuples of elements at strictly increasing index positions: (0,1), (0,2), (1,2) and so on. It never compares two elements, never hashes one, and never sorts. Every surprising behaviour people report about it is a restatement of that one design fact. ```python from itertools import combinations list(combinations(['b', 'a', 'a'], 2)) # [('b','a'), ('b','a'), ('a','a')] ``` Three tuples come out because there are three index pairs, C(3,2) = 3. The first two are equal as values, since positions 1 and 2 hold equal elements. Nothing has gone wrong: the count is always exactly the binomial coefficient of the input length, regardless of how many elements are equal. ### Why output order looks sorted in every tutorial Because index pairs are produced in increasing order, the output order is the input's own order lifted to tuples. If the input happens to be sorted, the output is lexicographically sorted, which is why every documentation example looks tidy. Hand it unsorted input and the output is just as deterministic but no longer lexicographic: ```python list(combinations(['c', 'a', 'b'], 2)) # [('c','a'), ('c','b'), ('a','b')] ``` The practical rule: **if downstream code depends on lexicographic order, sort the input yourself.** Do not rely on the function to do it; it will not, and the bug appears only once someone changes how the input list is built. The same reasoning applies to `itertools.permutations` and to `itertools.combinations_with_replacement`, which are built from the same positional machinery. ### Getting distinct results There are two honest strategies, and they differ in cost. 1. **Deduplicate the input first.** `combinations(sorted(set(items)), r)` produces distinct tuples in lexicographic order, and — crucially — it *shrinks the enumeration*: fewer input elements means a smaller binomial coefficient, so you do less work, not just less output. 2. **Deduplicate the output.** `set(combinations(items, r))` also produces distinct tuples, but it pays for the entire original enumeration first and then discards the surplus. It is the right choice only when the tuples must reflect distinct *positions* for some other reason, or when the input contains unhashable elements that cannot be put in a set beforehand. When elements are equal in value but carry distinguishing identity — two invoice lines with the same amount but different ids — the duplicates are usually not duplicates at all, and deduplicating would be the bug. Decide deliberately which of the two you have. ### The neighbour that actually repeats an element A common conflation: `('a','a')` appearing in the output above does **not** mean `combinations` reuses an element. It picked two different positions that happened to hold equal values. The function that genuinely pairs an element with itself is `itertools.combinations_with_replacement`: ```python from itertools import combinations_with_replacement list(combinations_with_replacement('ab', 2)) # [('a','a'), ('a','b'), ('b','b')] ``` Here the input has two distinct elements and one output tuple still repeats `'a'`, because the selection allows non-decreasing index positions rather than strictly increasing ones. Its count is C(n + r - 1, r), not C(n, r): for n=2, r=2 that is three, not one. Reach for it when the same option may legitimately be chosen more than once — allocating three identical slots from a menu of choices, or enumerating multisets. ### Putting the four functions on one grid Two independent questions place every combinatorial function in `itertools`: * May an element be reused within one tuple? * Does the arrangement of the chosen elements matter? No/No is `combinations`. No/Yes is `permutations`. Yes/No is `combinations_with_replacement`. Yes/Yes is `product` with `repeat=`. Being able to draw that two-by-two grid on a whiteboard, with a three-element example under each cell, is the answer an interviewer is looking for when they open with a duplicates question. ### The review habit In code review, the tell is a call to `combinations` over a list built from records rather than from a deduplicated key set, followed by downstream code that assumes each result is unique. Either the duplicates are meaningful, in which case say so in a comment, or the input should have been reduced to distinct keys before the call — and reducing it first is both cheaper and clearer.