| name | combinatorial |
| description | Use when solving problems involving permutations, combinations, backtracking, branch and bound, subset generation, and constraint satisfaction. Covers N-Queens, Sudoku solving, generating functions, and pruning strategies. Based on Knuth's TAOCP Vol. 4A.
USE FOR: permutation and combination generation, backtracking algorithm design, constraint satisfaction problems, branch and bound optimization, subset enumeration, pruning strategy selection
DO NOT USE FOR: graph traversal (use graph-algorithms), optimization with overlapping subproblems (use dynamic-programming)
|
| license | MIT |
| metadata | {"displayName":"Combinatorial Algorithms","author":"Tyler-R-Kendrick"} |
| compatibility | claude, copilot, cursor |
| references | [{"title":"The Art of Computer Programming, Vol. 4A: Combinatorial Algorithms — Donald Knuth","url":"https://www-cs-faculty.stanford.edu/~knuth/taocp.html"},{"title":"Combinatorial Optimization — Wikipedia","url":"https://en.wikipedia.org/wiki/Combinatorial_optimization"}] |
Combinatorial Algorithms
Overview
Combinatorial algorithms deal with counting, generating, and optimizing discrete structures -- permutations, combinations, subsets, partitions, and arrangements subject to constraints. Knuth devoted The Art of Computer Programming, Volume 4A: Combinatorial Algorithms, Part 1 entirely to this topic, calling combinatorics "the mathematics of choice." This skill covers the core techniques for systematic enumeration, backtracking search, and constraint satisfaction.
Fundamental Counting
Permutations
An ordered arrangement of n elements. The number of permutations of n distinct elements is n! (n factorial).
- All permutations of n elements: n!
- k-permutations of n elements (ordered selection of k from n): n! / (n - k)!
- Permutations with repetition: n! / (n1! * n2! * ... * nk!) where ni is the count of each repeated element.
Combinations
An unordered selection of k elements from n. The number of combinations is C(n, k) = n! / (k! * (n - k)!).
- With repetition (multiset coefficient): C(n + k - 1, k)
Subsets
The power set of a set with n elements has 2^n subsets. Each element is either included or excluded.
Backtracking
Backtracking is a systematic method for generating all (or some) possible configurations of a search space by incrementally building candidates and abandoning a candidate ("backtracking") as soon as it is determined that it cannot lead to a valid solution.
Backtracking Template
BACKTRACK(state, choices):
if state is a complete solution:
process(state)
return
for each choice in choices:
if is_valid(state, choice): // pruning check
apply(state, choice)
BACKTRACK(state, remaining_choices)
undo(state, choice) // backtrack
Key elements:
- State: The current partial solution being built.
- Choices: The decisions available at each step.
- Constraints: Rules that determine whether a partial solution is valid.
- Goal: The condition that identifies a complete solution.
Time Complexity
Backtracking explores a search tree. Without pruning, the worst case is O(b^d) where b is the branching factor and d is the depth. Effective pruning can dramatically reduce this in practice.
Classic Backtracking Problems
N-Queens
Place n queens on an n x n chessboard so that no two queens threaten each other (no shared row, column, or diagonal).
- Approach: Place queens one row at a time. For each row, try each column; prune if the column or either diagonal is already attacked.
- State: Positions of queens placed so far.
- Pruning: Track occupied columns and diagonals with sets or arrays.
- Solutions: 1 for n=1, 0 for n=2 and n=3, 2 for n=4, 10 for n=5, 92 for n=8.
Sudoku Solving
Fill a 9x9 grid so that each row, column, and 3x3 box contains digits 1-9 exactly once.
- Approach: Find the next empty cell, try each digit 1-9, prune if the digit violates row/column/box constraints.
- State: The partially filled grid.
- Pruning: Check row, column, and box constraints before placing each digit. Advanced: propagate constraints (naked singles, hidden singles) to reduce the search space before branching.
Subset Sum
Determine whether a subset of a given set sums to a target value.
- Approach: For each element, decide to include or exclude it. Prune branches where the running sum already exceeds the target (for positive numbers) or where the remaining elements cannot possibly reach the target.
Branch and Bound
Branch and bound is an enhancement of backtracking for optimization problems. It maintains a bound (upper or lower, depending on minimization vs maximization) and prunes branches that cannot improve upon the best solution found so far.
Framework
BRANCH_AND_BOUND(state):
if state is a complete solution:
update best_solution if state is better
return
if bound(state) cannot improve on best_solution:
return // prune
for each choice in choices:
apply(state, choice)
BRANCH_AND_BOUND(state)
undo(state, choice)
Key elements:
- Bounding function: A fast estimate of the best possible solution achievable from the current state.
- Pruning: Skip entire subtrees when the bound proves they cannot contain a better solution.
Applications: Traveling Salesman Problem, Integer Linear Programming, Job Scheduling, Knapsack (branch and bound variant).
Subset Generation
Iterative (Bitmask) Approach
Generate all 2^n subsets by iterating from 0 to 2^n - 1, where each bit indicates inclusion/exclusion.
GENERATE_SUBSETS(S):
n = |S|
for mask = 0 to 2^n - 1:
subset = {S[i] for each bit i set in mask}
process(subset)
Recursive Approach
For each element, recursively generate subsets that include it and subsets that exclude it.
SUBSETS(S, index, current):
if index == |S|:
process(current)
return
SUBSETS(S, index + 1, current) // exclude S[index]
SUBSETS(S, index + 1, current + {S[index]}) // include S[index]
Constraint Satisfaction Problems (CSP)
A CSP is defined by:
- Variables: The unknowns to be assigned values.
- Domains: The possible values for each variable.
- Constraints: Rules restricting which combinations of values are valid.
Solving Strategies
| Strategy | Description |
|---|
| Backtracking search | Assign variables one at a time, backtrack on constraint violation |
| Forward checking | After each assignment, remove inconsistent values from neighboring domains |
| Arc consistency (AC-3) | Propagate constraints to prune domains before and during search |
| Variable ordering (MRV) | Choose the variable with the Minimum Remaining Values (most constrained) first |
| Value ordering (LCV) | Try the Least Constraining Value first (preserves options for other variables) |
Examples: Sudoku, map coloring, scheduling, crossword puzzles, register allocation.
Generating Functions (Conceptual)
Generating functions are a powerful mathematical tool from combinatorics that encode a sequence of numbers as coefficients of a formal power series. While primarily a theoretical tool, they provide closed-form solutions and identities for counting problems.
- Ordinary generating function (OGF): A(x) = sum of a_n * x^n. Used for combinations and selections.
- Exponential generating function (EGF): A(x) = sum of a_n * x^n / n!. Used for permutations and labeled structures.
Practical insight: Even without computing generating functions directly, understanding them helps recognize when a counting problem has a known closed-form solution or recurrence. Knuth uses generating functions extensively in TAOCP to derive exact formulas for combinatorial quantities.
Example: The generating function for the number of ways to make change for n cents using coins of denominations d1, d2, ..., dk is the product of 1/(1 - x^di) for each denomination. The coefficient of x^n gives the answer.
Pruning Strategies
Effective pruning is what makes backtracking practical for large search spaces.
| Strategy | Description | Example |
|---|
| Constraint propagation | Reduce domains based on current assignments | Sudoku: eliminate placed digits from row/col/box |
| Bound pruning | Skip branches that cannot beat the current best | Branch and bound: skip if optimistic bound <= best |
| Symmetry breaking | Avoid exploring configurations that are equivalent by symmetry | N-Queens: fix the first queen to the left half |
| Dominance pruning | Skip states that are provably worse than another explored state | Knapsack: skip items with worse value-to-weight ratio |
| Feasibility pruning | Abandon states that cannot possibly lead to a valid solution | Subset sum: prune if remaining elements cannot reach target |
| Ordering heuristics | Process choices in an order likely to find solutions or prune early | MRV for CSPs, try larger values first for optimization |
Complexity of Combinatorial Problems
| Problem | Brute Force | With Pruning / Optimization |
|---|
| All permutations | O(n!) | O(n!) -- must enumerate all |
| All subsets | O(2^n) | O(2^n) -- must enumerate all |
| N-Queens (all solutions) | O(n!) | Significantly less with pruning |
| Sudoku | O(9^81) theoretical | Practical with constraint propagation |
| Subset Sum | O(2^n) | Pseudo-polynomial DP: O(n * target) |
| TSP (exact) | O(n!) | O(n^2 * 2^n) with DP (Held-Karp) |
| Graph Coloring | O(k^n) | NP-complete; effective with backtracking + pruning |
Knuth's TAOCP Vol. 4A: Key Topics
| Section | Topic |
|---|
| 7.2.1 | Generating all n-tuples |
| 7.2.1.1 | Generating all permutations |
| 7.2.1.2 | Generating all combinations |
| 7.2.1.3 | Generating all partitions |
| 7.2.1.4 | Generating all set partitions |
| 7.2.1.5 | Generating all trees |
| 7.2.2 | Backtrack programming |
| 7.2.2.1 | Dancing links (Algorithm X) |
Dancing Links (DLX): Knuth's Algorithm X with the "dancing links" technique is an efficient backtracking method for exact cover problems. It represents the constraint matrix as a doubly-linked list structure that allows O(1) removal and restoration of elements, making it highly efficient for problems like Sudoku, pentomino tiling, and N-Queens.
Best Practices
- Always add pruning to backtracking -- even simple feasibility checks can reduce runtime by orders of magnitude.
- For optimization problems, consider branch and bound before exhaustive enumeration.
- Use constraint propagation (forward checking, arc consistency) for CSPs to reduce the effective search space.
- Choose variable and value ordering heuristics carefully -- MRV and LCV are strong general-purpose strategies.
- Consider whether the problem has symmetries that can be exploited to avoid redundant exploration.
- For problems with overlapping subproblems (e.g., subset sum, TSP), combine backtracking with dynamic programming.
- Reference Knuth's TAOCP Vol. 4A for the most rigorous and comprehensive treatment of combinatorial generation and backtracking, including Algorithm X and dancing links for exact cover problems.
