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.