Combinatorial

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:

1. State: The current partial solution being built.
2. Choices: The decisions available at each step.
3. Constraints: Rules that determine whether a partial solution is valid.
4. 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:

1. Bounding function: A fast estimate of the best possible solution achievable from the current state.
2. 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

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.

Complexity of Combinatorial Problems

Knuth's TAOCP Vol. 4A: Key Topics

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.