Distinct Arrangements
Problem
Given a list of values that may contain repeats, return every distinct ordering of all of them. Two orderings are the same when they read the same value by value, so repeats must not produce duplicate answers. Return the orderings in ascending lexicographic order so the output is predictable.
Examples
Input: vals = [1, 2, 1]
Output: [[1, 1, 2], [1, 2, 1], [2, 1, 1]]
Why: 3 slots with two equal values give 3!/2! = 3 orderingsInput: vals = [2, 2, 2]
Output: [[2, 2, 2]]
Why: every ordering reads the sameInput: vals = []
Output: [[]]
Why: edge case, there is exactly one way to arrange nothingHints
0 / 3
Generating every ordering and removing duplicates afterwards works, but it can do far more work than there are answers. Stop duplicates from being built at all.
Sort the values first so equal ones sit side by side. Then two equal values are interchangeable, and you only need one fixed rule for which copy is used first.
Backtrack with a used flag per position. At each level, skip a value if it is already used, and also skip it if the value just before it is equal and not currently used, which forces equal copies to be placed left to right.
Solution
This is the used-set permutation search with one extra pruning rule. After sorting, equal values are adjacent, and allowing a copy only when its left twin is already on the path means equal copies always appear in their original order. Every distinct ordering therefore has exactly one way to be built, so no duplicate is ever produced and no set is needed to remove them. Trying values in sorted order at every level also makes the results come out in lexicographic order. Time is O(n × n!) in the worst case, and space is O(n) besides the output.
def arrangements(vals):
vals = sorted(vals) # equal values become neighbours
used, path, out = [False] * len(vals), [], []
def place():
if len(path) == len(vals):
out.append(path[:])
return
for i, v in enumerate(vals):
if used[i]:
continue
if i and v == vals[i - 1] and not used[i - 1]:
continue # a twin goes only after its left twin
used[i] = True
path.append(v)
place()
path.pop()
used[i] = False
place()
return out
print(arrangements([1, 2, 1])) # -> [[1, 1, 2], [1, 2, 1], [2, 1, 1]]
print(arrangements([2, 2, 2])) # -> [[2, 2, 2]]
print(arrangements([])) # -> [[]]Stuck on the idea rather than the code? Permutations covers it.