Trace Every Ordering of Three Items

Listing every ordering of a set, its permutations, is backtracking where each level of the tree fills one more position with an item not yet used. This walkthrough traces the search on 1, 2 and 3 from the empty path to the sixth ordering, showing the path after every choice and every undo.

The search keeps the shared path and a used flag per item, so it can skip items already placed. At each call it records a copy if the path holds all three items; otherwise it loops over the items, and for each unused one it marks it used and appends it (choose), searches (explore), then removes it and clears the flag (unchoose). The loop takes items in the order 1, 2, 3.

A run printed the path after every choice and every undo. Its first ten lines cover every ordering that starts with 1.

Every unchoose shortens the path by exactly one item, so on return each call finds the path as it left it. At change 5 the path is back to 1, and the loop at the second position moves on to 3, the next unused item. At change 10 it is empty again, and the first position moves on to 2. The same pattern repeats for 2 and 3, which the run printed in full: 30 changes in all, 15 choices and 15 undos, one for each node below the root of the tree.

The tree has 16 nodes: the start, 3 choices for the first position, 2 for the second under each, and 1 for the third, giving 3 × 2 × 1 = 6 leaves. The orderings were recorded in the order the leaves appear, left to right: 1 2 3, 1 3 2, 2 1 3, 2 3 1, 3 1 2, 3 2 1. Each leaf recorded a copy of the path, not the path itself, because the path was emptied again by the end.