Orderings when values repeat
List the different orderings of numbers that may repeat, without listing the same ordering twice, by sorting and skipping a value that repeats its unused twin. About 18 minutes.
Sort, then skip the twin
If the numbers include repeats, such as 1, 1, 2, the plain method lists the same ordering several times, once for each way of swapping the identical copies. You want each different ordering once.
First sort the numbers, so equal values sit side by side. Then add a rule: do not use a copy if the copy just before it, with the same value, is still unused.
if i > 0 and nums[i] == nums[i - 1]:
continue # same as the one beforeStart with the first 3. Then 3 and 5 follow: 3,3,5 and 3,5,3.
Why only the earlier twin matters
The rule forces equal copies to be used in the order they appear. When you are about to use the second copy of a value and the first is still free, you would be choosing the second before the first, which is a swapped duplicate of a path through the first. So skip.
If the first copy is already used higher up, taking the second is the natural next step and must be allowed. The output follows the sorted order of the values.
used[i] = True placed = nums[i]
At some position, the candidate has the same value as the item before it in the sorted list, and that earlier item is unused. What do you do?
- ASkip the candidate
- BUse it
- CUse both
Show the answer
Skip the candidate. Using it first would duplicate an ordering that uses the earlier twin first.
Permutations with duplicates
Given an array nums that may contain duplicate values, return all the different orderings (permutations) of its values, with no ordering listed twice. First sort nums, then list the orderings in the order that results from choosing, at each position, the unused values from the smallest to the largest.
nums = [1, 1, 2] → [[1, 1, 2], [1, 2, 1], [2, 1, 1]]
1 ≤ length of nums ≤ 7 · -10 ≤ nums[i] ≤ 10