Arrangements: Every Order With a Used List
A courier has parcels for three friends, Ana, Ben and Cy, and wants to compare every possible order of visits before choosing a route. Subsets asked "which items?"; this asks "in which order?" The tree changes shape, but the choose, explore, un-choose rhythm stays exactly the same.
The rule
Fill one slot at a time from what's unused, then hand it back.
Instead of deciding item by item, decide slot by slot: who is visited first, then second, then third. For each slot, try every person not already placed. A used list remembers who is placed, so nobody appears twice.
def orderings(items):
result, path = [], []
used = [False] * len(items)
def explore():
if len(path) == len(items): # every slot filled
result.append(path[:])
return
for i, item in enumerate(items):
if used[i]:
continue # already placed in an earlier slot
used[i] = True # choose
path.append(item)
explore()
path.pop() # un-choose: undo BOTH changes
used[i] = False
explore()
return resultThe first slot has n options, the second n − 1, and so on, so there are n × (n − 1) × … × 1 orderings: n factorial, written n!. That grows even faster than 2ⁿ: 10 items already give 3,628,800 orderings, so permutation problems come with very small limits.
Compare the two shapes side by side:
- Subsets: one level per item, two branches each (take or leave), 2ⁿ leaves. Order does not matter.
- Orderings: one level per slot, one branch per unused item, n! leaves. Order is the whole point.
One caution: if two items are identical, such as two parcels for the same address, this code lists some orderings twice. That calls for an extra skip rule, in the same spirit as skipping a repeated fixed value in the triples lesson.
The shortcut
Before writing any backtracking, ask "does order matter?" If [Ben, Ana] and [Ana, Ben] are different answers, you want orderings and a used list. If they are the same answer, you want subsets or combinations, which never go back to earlier items.
Slot 1: Ana
Mark Ana used. Slot 2 can be Ben or Cy.
The trap is undoing only half the choice. Pop the path but forget used[i] = False, and that person stays "used" forever, so later branches run out of people.
Drills
Answer fast — trust the rule.
How many orderings does orderings produce for 4 items?
What is the second ordering orderings(["Ana", "Ben", "Cy"]) records?
The line used[i] = False is deleted. What does orderings(["A", "B", "C"]) return?
"List every way to choose 2 of these 5 books to take on holiday." Does order matter?
Remember
- Fill one slot at a time from what's unused, then hand it back.
- Shortcut: ask "does order matter?"; yes means orderings with a
usedlist. - Trap: undoing the path but not the
usedmark.