Rooftop sweep

A dispatcher picks the route by eye from the full list of orders. Four pads is twenty-four lines, and the list has to be generated.

The problem

A parcel drone serves a handful of rooftop pads, each painted with a two-character code. In one sortie it visits every pad on the manifest exactly once, in whatever order the dispatcher sets, then returns to the depot. Cranes and window cleaners rule out some orders on the day, so the dispatcher wants the whole list on screen.

Produce every visiting order. Two orders differ when the drone reaches the pads in a different sequence. Write each as the codes joined by -, and return the list sorted alphabetically, so today's can be diffed against yesterday's.

Input. pads — a list of distinct pad codes, in manifest order.

Output. Every visiting order as a - joined string, sorted alphabetically.

Example.

pads = ["H4", "K2", "M9"]

->  ["H4-K2-M9", "H4-M9-K2", "K2-H4-M9",
     "K2-M9-H4", "M9-H4-K2", "M9-K2-H4"]

Three pads give 3 × 2 × 1 = 6 orders: three codes could go first, two remain for the second slot, one for the last slot.

A second example, which sorting rearranges:

pads = ["A1"]         ->  ["A1"]
pads = ["B7", "A1"]   ->  ["A1-B7", "B7-A1"]

A manifest of one has one order, not none. The two-pad answer is not in manifest order, because the output is sorted.

Constraints.

• 1 <= len(pads) <= 8, so at most 8! = 40,320 orders
• codes are distinct: a letter then a digit

Hints

Approach

Brute force

Generate every sequence of n codes — n choices in each of n slots, nⁿ in all — and throw away those naming a pad twice. For eight pads that is 8⁸ = 16,777,216 candidates for 40,320 valid orders: 415 rejects per keeper, each detected only after the whole sequence is built.

The insight

Choosing a pad for this slot only removes it from the pool, so mark it taken, recurse on what is left, then clear the mark — one shared buffer walks every order without copying the manifest.

Clearing the mark is what the word backtracking names. The mark means "on the route being built right now", never "seen at some point in the search", because a pad that sits third in one order sits first in another. The codes are distinct, so each order matches one path down the tree and none is produced twice.

Algorithm

1. Keep route, the codes chosen so far, and booked, one flag per pad.
2. If route is as long as the manifest, join it with - and record it.
3. Otherwise, for each pad j whose flag is clear: set the flag, append the code, recurse.
4. On return, pop the code and clear the flag; move to the next j.
5. Sort the collected strings.

Complexity

Time O(n · n!) — n! orders, each O(n) to join, with the interior of the tree a constant factor above the leaves; the sort adds a log n! factor on the comparisons. Nothing beats n!, because the output is n! lines. Space O(n) for the stack, the flags and the buffer.

Solution

"""Rooftop sweep — every visiting order by choose, recurse, un-choose."""


def solve(pads):
    orders = []
    route = []
    booked = [False] * len(pads)    # booked[j]: pad j is already on this route

    def extend():
        # invariant: `route` is a valid partial sweep and `booked` marks exactly
        # the pads it contains, so any unmarked pad is a legal next stop.
        if len(route) == len(pads):
            orders.append("-".join(route))
            return
        for j, pad in enumerate(pads):
            if booked[j]:
                continue
            booked[j] = True
            route.append(pad)
            extend()
            route.pop()
            booked[j] = False       # free again for the branches still to come

    extend()
    return sorted(orders)

TESTS = [
    ((["H4", "K2", "M9"],), [
        "H4-K2-M9", "H4-M9-K2", "K2-H4-M9",
        "K2-M9-H4", "M9-H4-K2", "M9-K2-H4",
    ]),
    ((["A1"],), ["A1"]),                       # one pad, one order, not zero
    ((["B7", "A1"],), ["A1-B7", "B7-A1"]),     # sorted, so not manifest order
    ((["P2", "Q5", "R1", "S8"],), [
        "P2-Q5-R1-S8", "P2-Q5-S8-R1", "P2-R1-Q5-S8", "P2-R1-S8-Q5",
        "P2-S8-Q5-R1", "P2-S8-R1-Q5", "Q5-P2-R1-S8", "Q5-P2-S8-R1",
        "Q5-R1-P2-S8", "Q5-R1-S8-P2", "Q5-S8-P2-R1", "Q5-S8-R1-P2",
        "R1-P2-Q5-S8", "R1-P2-S8-Q5", "R1-Q5-P2-S8", "R1-Q5-S8-P2",
        "R1-S8-P2-Q5", "R1-S8-Q5-P2", "S8-P2-Q5-R1", "S8-P2-R1-Q5",
        "S8-Q5-P2-R1", "S8-Q5-R1-P2", "S8-R1-P2-Q5", "S8-R1-Q5-P2",
    ]),
]

Pitfalls

• Recording route instead of the joined string. The list ends up holding n! references to one buffer, empty by the time it is printed.
• Not clearing the flag on the way back up. The first order comes out right and the search then starves: three pads give one order instead of six, because every pad the first branch used stays marked.
• Swapping codes inside pads and forgetting to swap back. The manifest is left permuted, so sibling branches enumerate a different manifest and codes vanish from the list.

Variants

• Tasting flight — the same tree, but each item is only in or out and order inside an answer means nothing.
• Backtracking — the lesson on the choose, recurse, un-choose loop.