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)
Instrucciones de origen · Vista previa de solo lectura
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)
[{"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 entirely to this topic, calling combinatorics "the mathematics of choice." This skill covers the core techniques for systematic enumeration, backtracking search, and constraint satisfaction.
The Art of Computer Programming, Volume 4A: Combinatorial Algorithms, Part 1
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)
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.
