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.
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
Worked example
- To build permutations of
[1,2,3], choose the first position from all three items. - If
1is placed first, mark it used and recurse to fill the second position from{2,3}. - After returning, unmark
1before 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 it
- 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.
Next recommended lesson
Continue through this topic with Least You Need to Know: Prefix Function, Borders, and KMP Intuition.
Least You Need to Know: Prefix Function, Borders, and KMP IntuitionRelated lessons
Keep going with nearby lessons in the same topic.