Permutations with duplicates
Picture
Permuting [1,1,2] by item position generates duplicate value sequences when the two 1s swap identities.
Predict
Should every repeated value be skipped globally?
Walk through the small example
No. Sorting makes equal sibling choices adjacent, and a depth-local rule removes symmetric branches.
Mental model and complete Python solution
Duplicates are not forbidden items; they are indistinguishable choices. Skip only the second twin when the first twin was available at this same branch point.
What the function promises: Return all distinct list permutations in lexicographic order.
def unique_permutations(values):
values = sorted(values)
used = [False] * len(values)
answer, path = [], []
def build():
if len(path) == len(values):
answer.append(path[:]); return
for i, value in enumerate(values):
if used[i] or (i and values[i] == values[i-1] and not used[i-1]): continue
used[i] = True; path.append(value)
build()
path.pop(); used[i] = False
build()
return answer
assert unique_permutations([1,1,2]) == [[1,1,2],[1,2,1],[2,1,1]]
assert unique_permutations([]) == [[]]
Work and storage: O(U·n) output work for U distinct permutations, plus O(n) active state.
When to recognize it: Sorting makes equal sibling choices adjacent, and a depth-local rule removes symmetric branches.
Check before applying it: Using a global value set loses required repeated copies; output size can still be enormous.
Change one rule
Return only the count.
See what changes
Use factorial counts divided by duplicate factorials instead of enumerating outputs.
Connect
backtracking: The prefix is built by choose, recurse, and undo.
Sorting: buy useful order: Sorting makes equivalent sibling choices detectable.