Generating permutations of a multiset, why must sort-and-skip test that the earlier twin is unused?

## Why duplicates appear at all A multiset is a collection that may contain repeated values. Take a playlist where the same track appears twice. The enumeration machinery does not know the two copies are the same thing: it sees candidate index 0 and candidate index 1, treats them as distinct, and happily produces both "copy A then copy B" and "copy B then copy A". As sequences of *values* those two results are identical, so the output contains the same ordering twice. Generalising: if the multiset contains a group of `k` identical items, every distinct output is generated `k!` times, once per internal arrangement of that group. Two twins doubles the output; three identical tracks sextuples it. And the cost is not just in the printing — each duplicate is a fully explored subtree, so the wasted work is proportional to the duplication factor. ## The canonical-choice fix The fix is the same idea used everywhere in enumeration: of the many search paths that produce the same result, allow exactly one and prune the rest at the node where they diverge. For identical items, choose this canonical rule: **within a group of equal items, they must be consumed left to right**. If the copy at index `i` and the copy at index `i-1` are equal, then placing `i` is only allowed when `i-1` has already been placed. Any branch that tries to place the right-hand twin first is a relabelling of a branch already explored, so it is cut. Expressed as a skip test inside the candidate loop, with the candidate list sorted so equal items are adjacent: > if `i > 0` and `a[i] == a[i-1]` and `used[i-1]` is false, skip `i`. Sorting is a precondition, not a nicety. The test only looks one position back, so it can only catch duplicates that are neighbours. On unsorted input the same value can be scattered and the guard silently misses most of it, leaving duplicates in the output. ## Trace the smallest case Two identical items, `a = [x, x]`. There is exactly one distinct ordering. With the correct guard: at the top level, index 0 is allowed (there is no earlier neighbour) and placing it marks index 0 used. At the next level index 1 is considered — its neighbour is equal, but that neighbour *is* used, so it is not skipped, and the ordering completes. Back at the top level, index 1 is now considered as a first pick: its neighbour is equal and unused, so it is skipped. One result. Correct. Now flip the condition to skip when the earlier twin *is* used. At the top level index 0 is placed. At the next level index 1 sees its equal neighbour as used and skips — the branch dead-ends without emitting anything. Back at the top, index 1 sees its equal neighbour unused and skips too. Total output: nothing at all. The reversed guard does not dedupe more aggressively; it makes it impossible to ever place the second member of a group, so every branch that needs a repeat dies. That asymmetry is the whole point of the question, and it is why "either direction works, one just prunes earlier" is a wrong answer worth being able to refute with the two-element trace. ## An alternative that needs no sort Sorting requires the items to be comparable, which is not always true. A second technique dedupes per level instead: at each recursion level, keep a set of values already tried in this loop, and skip a candidate whose value is already in it. Different levels get different sets. This is equivalent in output and needs only equality rather than ordering. The costs are a set allocated per level — extra memory proportional to depth times branching — and the loss of lexicographic output order that a sorted candidate list gives you for free. Choose it when items cannot be ordered or when the input arrives unsorted and sorting it would disturb something else. ## The same guard for unordered selections When you are choosing groups rather than orderings, the same canonical idea applies with a simpler test. In a search that carries a start index and loops `i` from `start`, skip a candidate that equals its predecessor **when it is not the first iteration of this loop**. The reasoning is identical: at a given level, trying the same value twice explores the same subtree twice. No availability markers are needed, because the increasing start index already prevents an item being reused. ## Why filtering afterwards is the wrong answer The tempting shortcut is to generate everything and deduplicate the results at the end. It is correct and it is the wrong trade. You have already paid to explore every duplicate subtree — a factor of `k!` per group of twins — and now you additionally hold or hash the entire inflated output. The guard costs one comparison per candidate and eliminates the subtree before it is entered. On a search that is already factorial in size, prune at the node, never filter at the leaf. ## What a strong answer sounds like Name the cause (interchangeable items produce relabelled duplicate paths), name the fix (a canonical left-to-right consumption order made local by sorting), state the guard, state both failure directions with their symptoms — missing guard means output inflated by `k!`, reversed guard means outputs disappear — and mention the per-level-set alternative for uncomparable items.