When order matters

Every item available at every level, and a marker to stop reusing the same one.

Key idea

No start index, a used marker instead

When different orderings are different answers, the start index goes away: every item is a candidate at every level. What replaces it is a record of which items are already placed in the current arrangement.

A boolean list parallel to the items is the usual form. It is set before the recursive call and cleared after it, which is the undo step applied to something other than the result being built.

What the marker buys you is that the pool of candidates shrinks as you descend. Below is one path straight down the tree, taking the first available item at every level, with no recursion in sight.

1items = ["a", "b", "c"]2used = [False, False, False]3 4for depth in range(len(items)):5    available = [index for index in range(len(items)) if not used[index]]6    taken = available[0]7    print(f"depth {depth}: may still place {[items[i] for i in available]},"8          f" taking {items[taken]}")9    used[taken] = True                  # choose10 11print("at the bottom, nothing is left:", used)

Three levels, and the branching factor falls by one each time, which is where n factorial comes from.

Find the bug· 5 min

Find the missing restoration

This is meant to produce every ordered pair of different items. On three items it returns two results instead of six. Click the line where a restoration is missing.

Click the line you think is wrong

Problem· 22 min

Permutations

Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.

1items = ["a", "b", "c"]2used = [False, False, False]3 4for depth in range(len(items)):5 available = [index for index in range(len(items)) if not used[index]]6 taken = available[0]7 print(f"depth {depth}: may still place {[items[i] for i in available]},"8 f" taking {items[taken]}")9 used[taken] = True # choose10 11print("at the bottom, nothing is left:", used)