Algorithms / Permutations Constraints Search

Least You Need to Know: Permutations, Used Sets, and Constraint Propagation

Permutation search cares about **order**, so each recursive level chooses the next position from items not yet used. Constraint checks can often be applied to the growing prefix to reject bad permutations early.

The least you need to know

Permutation backtracking chooses the next position from elements not yet used in the current prefix.
A used set, used array, or in-place swap is a standard way to avoid reusing the same element twice.
Prefix constraints can often be checked before the permutation is complete.
When order matters, `[a,b]` and `[b,a]` are different outcomes and should be explored separately.
Duplicate values require extra care so the same permutation is not emitted multiple times.

Key notation

prefix already fixed first part of the permutation

used[x] whether item x is already placed

constraint propagation reject a partial permutation as soon as its prefix breaks a rule

Tiny worked example

To build permutations of `[1,2,3]`, choose the first position from all three items.
If `1` is placed first, mark it used and recurse to fill the second position from `{2,3}`.
After returning, unmark `1` before trying another first choice.
If a prefix already violates a rule, reject it before filling later positions.

Common mistakes

Students often use a subset template for permutations and accidentally ignore order.
Students often forget to track which elements are already used in the current prefix.
Students often wait until the end to check an obvious prefix conflict and lose pruning opportunities.

How to recognize this kind of problem

The prompt asks for arrangements, orderings, seatings, or permutations.
A partial prefix can already violate an adjacency or placement rule.
Each level chooses the next position rather than include versus exclude.