Permutations and Handling Duplicates
25 min · Intermediate
Need help? Ask a tutor on WhatsApp (opens in a new tab)Orders matter in many problems: the order in which tasks run, the seats in a row, the steps of a route. A permutation uses every item once in some order. The search is the same template as before, with one new idea: remember which items are already used.
Permutations with a used list
Permutation is one ordering of all the items in a list. A list of n distinct items has n factorial permutations, which is n x (n - 1) x ... x 1.
A scheduler lists every order in which 3 tasks can run. Unlike a subset, every task may go in any position, but only once. A used list marks the tasks already in the path.
def permutations(items): result, used = [], [False] * len(items) def walk(path): if len(path) == len(items): result.append(path[:]) return for i, item in enumerate(items): if not used[i]: used[i] = True # choose path.append(item) walk(path) path.pop() # undo used[i] = False walk([]) return resultExample 1 · Orders for three tasks
import itertools
def orders(items): result, used = [], [False] * len(items) def walk(path): if len(path) == len(items): result.append(path[:]) return for i, item in enumerate(items): if not used[i]: used[i] = True # choose path.append(item) walk(path) path.pop() # undo used[i] = False walk([]) return result
mine = orders(["A", "B", "C"])print(["".join(p) for p in mine])print(mine == [list(p) for p in itertools.permutations(["A", "B", "C"])])['ABC', 'ACB', 'BAC', 'BCA', 'CAB', 'CBA'] True
What this code does
- The used-list search tries items in list order, so the answers come out in the same order as
itertools.permutations. - Six orders appear, which is 3 x 2 x 1.
jointurns each list into a short word so the six orders fit on one line.
Example 2 · Brute force: build all, then filter
from itertools import permutations
orders = [p for p in permutations("ABC") if p.index("A") < p.index("B")]print(len(orders))print(["".join(p) for p in orders])3 ['ABC', 'ACB', 'CAB']
What this code does
- Task A must run before task B. Build every order and keep the ones where A comes first.
- Three of the six orders survive. This is simple and right, but it builds all n factorial orders even when most are rejected.
Two things are undone after the recursive call: the path and the used flag. Three tasks give 3 x 2 x 1 = 6 orders.
Swapping in place
Interviews often show a version without a used list. Swap each later item into the current position, recurse, then swap back. The list itself is the path.
def permutations(items): result = [] def walk(pos): if pos == len(items): result.append(items[:]) return for i in range(pos, len(items)): items[pos], items[i] = items[i], items[pos] walk(pos + 1) items[pos], items[i] = items[i], items[pos] walk(0) return resultExample 3 · Swapping in place
def permutations(items): result = [] def walk(pos): if pos == len(items): result.append(items[:]) return for i in range(pos, len(items)): items[pos], items[i] = items[i], items[pos] walk(pos + 1) items[pos], items[i] = items[i], items[pos] walk(0) return result
print(permutations([1, 2, 3]))[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 2, 1], [3, 1, 2]]
What this code does
- Position 0 takes each item in turn, then position 1 does the same for the items that are left.
- The swap after the recursive call is the undo.
- The same six orders appear as with the used list, in a different order.
Items before pos are fixed and the rest are still free. Tuple unpacking swaps two items in one line. The answers come out in a different order from the used-list version.
Duplicates: skip repeats at the same level
Duplicate skipping is a check that ignores a value equal to the previous one at the same level of the search. It needs sorted input and removes repeated answers without building them.
With the input [1, 2, 2] the search would build [1, 2] twice, once for each 2. Sort the input, then skip an item that equals the one just before it at the same level.
def unique_subsets(nums): nums = sorted(nums) result = [] def walk(start, path): result.append(path[:]) for i in range(start, len(nums)): if i > start and nums[i] == nums[i - 1]: continue # same value at this level path.append(nums[i]) walk(i + 1, path) path.pop() walk(0, []) return resultExample 4 · Duplicates make repeated answers
def permutations(items): result, used = [], [False] * len(items) def walk(path): if len(path) == len(items): result.append(path[:]) return for i, item in enumerate(items): if not used[i]: used[i] = True # choose path.append(item) walk(path) path.pop() # undo used[i] = False walk([]) return result
result = permutations([1, 1, 2])print(len(result))print(len({tuple(r) for r in result}))6 3
What this code does
- The two 1s sit at different positions, so the search treats them as different items.
- Six orders are built, but only three are different: the answer [1, 1, 2] shows up twice, and so do the others.
- Turning each list into a tuple lets a set count the different ones.
i > start lets the first candidate of a level through, and only later equal values are skipped. A repeated value can still be used deeper, so [2, 2] is kept.
Unique permutations with a Counter
For permutations of [1, 1, 2], count how many of each value are left. At each level try every distinct value once, and take one from its count while you explore it.
from collections import Counter
def unique_permutations(items): left, result = Counter(items), [] def walk(path): if len(path) == len(items): result.append(path) return for value in sorted(left): if left[value]: left[value] -= 1 walk(path + [value]) left[value] += 1 walk([]) return resultExample 5 · Unique subsets of [1, 2, 2]
def unique_subsets(nums): nums = sorted(nums) result = [] def walk(start, path): result.append(path[:]) for i in range(start, len(nums)): if i > start and nums[i] == nums[i - 1]: continue # same value at this level path.append(nums[i]) walk(i + 1, path) path.pop() walk(0, []) return result
print(unique_subsets([2, 1, 2]))print(len(unique_subsets([2, 1, 2])), "instead of", 2 ** 3)[[], [1], [1, 2], [1, 2, 2], [2], [2, 2]] 6 instead of 8
What this code does
- Sorting turns [2, 1, 2] into [1, 2, 2], so the equal values are neighbours.
- [2] appears once and [2, 2] appears once, as they should.
- Six different subsets exist, while the plain method would list eight.
Example 6 · Unique permutations with a Counter
from collections import Counter
def unique_permutations(items): left, result = Counter(items), [] def walk(path): if len(path) == len(items): result.append(path) return for value in sorted(left): if left[value]: left[value] -= 1 walk(path + [value]) left[value] += 1 walk([]) return result
print(unique_permutations([1, 1, 2]))print(len(unique_permutations(list("aabb"))))[[1, 1, 2], [1, 2, 1], [2, 1, 1]] 6
What this code does
- Only three different orders exist for [1, 1, 2], and the Counter search builds exactly those.
- For "aabb" the answer is 4! / (2! x 2!) = 6, instead of 24.
path + [value] makes a new list for each call, so only the counter needs an undo. Every answer is already a separate list.
How fast the answers grow
n items have n factorial orderings: 8 items give 40 320 and 10 give 3 628 800. A test with a 2 second limit can handle the first but not the second. itertools.permutations is quicker per answer, not fewer.
from itertools import permutationsfrom math import factorial
print(factorial(8), factorial(10))print(list(permutations("abc", 2)))print(len(set(permutations("aab"))))Example 7 · Growth and the set trap
from itertools import permutationsfrom math import factorial
for n in range(3, 11): print(n, factorial(n))print(len(set(permutations("aabb"))))print(factorial(4) // (factorial(2) * factorial(2)))3 6 4 24 5 120 6 720 7 5040 8 40320 9 362880 10 3628800 6 6
What this code does
- The count grows by a larger factor at every step, so keep n at about 8 or less when you list every order.
set(permutations(...))gives 6 different orders, but it first walks all 24.- The formula n! divided by the factorial of each repeat count gives the same 6 directly.
permutations(items, r) orders r items out of the list. set(...) removes repeats, but only after all n factorial orderings were built.
Next step
Check your understanding
11 quick questions