Permutations

The problem it solves

Produce every ordering of a collection: for [1, 2, 3], all six of 123, 132, 213, 231, 312, 321. Seatings, schedules, tour orders, brute force over small arrangement spaces — and the second canonical backtracking exercise, one notch harder than subsets because the state being mutated is richer: not a membership list but the array itself, rearranged in place and restored, swap by swap.

The count is n-factorial, and factorials are violent: 3! = 6, 5! = 120, 10! = 3.6 million, 13! overflows a 32-bit integer. The two counting prompts at the start of the trace — how many orderings, and how many start with a given element — are asked because both identities ((n)! and (n−1)!) do real work in interviews far beyond enumeration: “how many arrangements satisfy X” questions are usually these two formulas wearing constraints.

The intuition — and where it breaks down

Fill the ordering one position at a time. For position 0, any of the n elements can lead; for position 1, any of the remaining n−1; and so on — which multiplies to n!. The swap-based implementation makes “the remaining elements” cost nothing to track: positions before k hold the chosen prefix; positions from k onward hold exactly the unused candidates. To try candidate a[i] in position k, swap it into place — one move partitions the array correctly for the recursion below. No used-set, no auxiliary anything: the array’s own arrangement is the bookkeeping.

The price of that elegance is the restore. After exploring everything under a choice, the identical swap runs again — a swap is its own inverse — returning the array bit-for-bit to what the next candidate expects. The player’s one choice-question fires exactly here, at the first restore, because this is where intuition most wants to cut the corner: “the next swap will overwrite it anyway” feels plausible and is precisely wrong. The next choose-swap composes with the current arrangement; without the restore, position k trades with the wrong resident, and the enumeration starts repeating some orderings and omitting others — silently, plausibly, and only detectably by counting.

Where the intuition breaks down further: the prefix is fixed for the current subtree only. The settled region the player draws behind position k is provisional — it will be unwound and refilled (n−k)! times. Confusing “fixed for this subtree” with “final” is the same mistake as reading a heap’s second level as sorted; the drawing’s region marks are scoped to the frame for exactly this reason.

Loading…

A walkthrough you can check

Permute [1, 2, 3], candidates tried left to right:

1. k=0, candidate 1 (swap with itself — no motion). k=1, candidate 2. k=2: leaf 123. Backtrack; k=1, candidate 3: swap positions 1↔2 → leaf 132. Restore swap.
2. Back at k=0: restore (nothing moved), next candidate 2: swap 0↔1 → array [2,1,3]. Under it: 213, then 231. Restore swap → [1,2,3].
3. Candidate 3: swap 0↔2 → [3,2,1]. Under it: 321, then 312. Restore → [1,2,3].

Six leaves, 3!, and the array ends exactly where it began — the final state of the bars in the player is the original input, which is the visible proof that every choose was un-chosen. Note the ordering of output: not lexicographic (see step 3: 321 before 312) — swap-based enumeration has its own order, and tests that assume sorted output will fail against a correct implementation. Sort the output, or use the insertion-based variant, when order is contractual.

The invariant

At a call with prefix length k: positions 0..k−1 hold the current subtree’s chosen prefix, positions k..n−1 hold precisely the elements not yet chosen (in some order), and when the call returns, the array is exactly as it was when the call began. The choose-swap maintains the partition (it moves one unused element into the prefix and the displaced prefix-boundary element into the unused zone); recursion below operates entirely on positions ≥ k+1 by the same invariant; and the restore-swap — the same two indices — undoes the single mutation this frame made. Frames therefore compose: each returns the world as found, which is the definition of backtracking done right.

Correctness of the enumeration follows: at each k every unused element is tried in position k exactly once (the loop over i), so paths biject with orderings — n! leaves, no repeats, no gaps. The unit suite checks a sharp corollary: every (a, b) swap pair appears an even number of times in the trace, choose matched with restore.

Complexity, derived

n! leaves; each leaf copies its ordering out at O(n); internal nodes do O(1) swaps — O(n! · n) time, which the output alone already demands. Space beyond output: O(n) recursion depth, O(0) extra data structures — the in-place swap trick’s entire selling point over the used-array version (which spends O(n) extra and a scan per level, same asymptotics, more moving parts).

Factorial growth deserves respect stated plainly: this is only ever run for n ≤ ~10. Beyond that, problems that sound like “all orderings” are answered by counting formulas, by next-permutation (O(n) per successor, no enumeration), or by search with pruning where most orderings are never touched. Recognising which of those a question wants — instead of reflexively enumerating — is the actual skill being probed.

What people get wrong

• Skipping the restore-swap — the silent corruption. Counting leaves (must equal n!) catches it; eyeballing output usually does not.
• Storing the live array instead of a copy at each leaf: every recorded “ordering” aliases one array holding the original input by the end.
• Assuming lexicographic output from the swap method — its order is its own. Sort if the contract cares.
• Duplicates unhandled: with repeated values, distinct paths produce identical orderings. The fix is a per-level “tried values” set (or sort + skip in the insertion variant) — subtler than the subsets dedup, and a common follow-up.
• Reaching for enumeration when next-permutation suffices: “the k-th ordering” and “the next ordering” have O(n) answers (factorial number system; the standard next-permutation algorithm) that never build the tree.

Implementation notes

The swap template: base case at k = n records a copy; loop i from k to n−1; swap(k, i); recurse(k+1); swap(k, i) again. Writing the two swaps as literally identical lines — same call, same arguments — is good practice and good communication: reviewers see the inverse pairing instantly.

The insertion-based alternative builds each permutation by choosing from an explicit remaining-list; it yields lexicographic order when the input is sorted and makes the duplicates-skip guard natural (skip equal neighbours), at the cost of O(n) list surgery per node. Heap’s algorithm, the third family member, generates each successive permutation from the previous by a single swap — minimal-change order, valuable when applying a permutation is expensive (hardware test patterns, combinatorial Gray-code arguments). Knowing the three variants’ orders — swap: unordered; insertion: lexicographic; Heap’s: minimal-change — lets you pick by requirement instead of by habit.

For “permutations of a multiset” counts without enumeration: n! divided by the product of the duplicates’ factorials — the formula interviews want when they say “how many distinct arrangements of the word BANANA” — and the bridge from this page’s tree to combinatorics proper.

The follow-up questions

Why does the swap version need no used-array? The array partitions itself: prefix = chosen, suffix = unused, and each swap maintains the partition. The data structure is the invariant.

Why must the restore be the identical swap? Swaps are self-inverse; re-running one restores the array exactly. Any other “cleanup” leaves the next candidate composing with a scrambled state — repeats and omissions follow.

How does Heap’s algorithm differ? One swap between consecutive permutations, versus potentially many here. Same n! output, minimal motion — chosen when applying each permutation dominates the cost.

The k-th permutation without enumerating? Factorial number system: the leading element is index k ÷ (n−1)! into the remaining list, recurse on the remainder. O(n²) naively, no tree — and the standard answer to “give me permutation number 400,000”.