Chapter 38: Combinatorial Algorithms

When does a subset-state representation beat naive exhaustive search?

An exact algorithm must find, count, or enumerate precisely the objects specified by its input. These are different tasks. A decision algorithm answers whether any object exists; an optimization algorithm returns a best object; a counting algorithm returns their number; an enumeration algorithm outputs them all. An efficient method for one task does not automatically give the same guarantee for another.

Consider $n$ workers and $n$ jobs with a binary compatibility matrix $A$. Entry $A_{ij}=1$ means worker $i$ may take job $j$. A valid assignment is a permutation $\pi$ with $A_{i,\pi(i)}=1$ for every worker. Brute force checks all $n!$ permutations, requiring $O(n\,n!)$ compatibility tests in a direct implementation. Recursive search can reject invalid prefixes earlier, but its worst-case search remains factorial when every assignment is permitted.

The key compression is to process workers in a fixed order. After assigning the first $i$ workers, future choices depend only on the set $S$ of used jobs, with $|S|=i$. Distinct prefixes ending with the same $S$ have the same remaining workers and jobs. Their histories need not be retained separately when the task is counting. Define $D(S)$ as the number of compatible assignments of the first $|S|$ workers onto exactly $S$. With workers indexed from zero,

$$ D(\varnothing)=1,\qquad D(S)=\sum_{j\in S}A_{|S|-1,j}D(S\setminus\{j\})\quad(S\ne\varnothing). $$

Partition assignments by the job of their last worker to prove the recurrence: each assignment has exactly one predecessor and contributes exactly once. There are $2^n$ states and at most $n$ predecessors per state, yielding $O(n2^n)$ arithmetic operations and $O(2^n)$ integer cells. The answer is $D([n])$. For eight workers, there are $40320$ permutations but only $256$ subset states. Compression is useful because many histories share the same future; it is not merely a different encoding of one search path.

Arithmetic operations are not automatically constant-time. Counts can reach $n!$, needing $B=O(n\log(n+1))$ bits. Straightforward exact additions and linear-cost operations on $n$-bit masks give the conservative bit bound $O(n2^nB)$ for positive $n$, with polynomial input validation additional. Dense input uses $n^2$ entries. Storing all counts uses $O(2^nB+n^2)$ bits. Empty input has one empty assignment, not zero.

For the concluding enumeration task, a different observation supplies the foundation. A prefix can be extended exactly when the residual worker–job bipartite graph has a perfect matching. This is testable in polynomial time using augmenting paths. A depth-first search that descends only into extendable prefixes has polynomial delay between outputs, including before the first output and after the last. Section 38.3 implements both methods, while the investigation proves their distinct bounds. The optional extensions refine states, transforms, parameters, and structural guarantees; no full algorithms or optimization course is required to complete the foundation.

38.1 Exhaustive enumeration and recursive search

Optional extension; not required to complete the chapter foundation.

A recursive search node is a partial object plus the information needed to continue it. For assignments, a node consists of the current worker index $i$, the used-job set $S$, and the chosen prefix. Its invariant is that the prefix assigns the first $i$ workers compatibly, without repeating a job, and $|S|=i$. Branching on every compatible unused job preserves the invariant.

Correctness requires soundness, completeness, and uniqueness. Every complete leaf is valid by the invariant. Every valid permutation follows a branch at every worker because its next job is compatible and unused. The fixed worker order gives one path for each assignment, so no duplicate outputs occur. These properties must be proved separately from runtime claims.

Solved example. On the motivating matrix, worker one may choose job one or two. After choosing one, worker two may choose two or three. Prefix $(1,2)$ finishes as $(1,2,3)$. Prefix $(1,3)$ fails because the only remaining job two is forbidden for worker three. After choosing job two first, worker two must take three, and worker three takes one. Thus exactly two leaves are successful. Local compatibility prunes some choices, but still explores a prefix with no completion.

For the all-ones matrix, every prefix is extendable. The number of partial assignments of length $i$ is $n!/(n-i)!$, so the full search tree has $\sum_{i=0}^n n!/(n-i)!$ nodes, which is $O(n!)$. Scanning all $n$ jobs at each internal node gives an $O(n\,n!)$ upper bound. Streaming the outputs uses polynomial working space, whereas storing them all requires at least their aggregate output size.

A state may be sufficient for decision or counting yet insufficient for listing actual histories without reconstruction. Merging all prefixes with the same job set is valid for their count, but an enumerator must recover each distinct prefix or reconstruct it on demand.

Exercise. For the all-ones $3\times3$ matrix, count nodes by depth. Hint: partial assignments are injective sequences. Solution: the levels have $1,3,6,6$ nodes, totaling sixteen. There are six complete assignments. Eight subset states suffice for a counting DP, while sixteen search nodes preserve the separate prefix histories.

38.2 Branch-and-bound and pruning techniques

Optional extension; not required to complete the chapter foundation.

Branch-and-bound solves optimization problems using a feasible incumbent and a bound valid for every completion of a partial state. For minimization, let $U$ be the cost of the best complete assignment found. If a prefix has accumulated cost $c$ and remaining workers $R$ and jobs $J$, a useful lower bound is

$$ \operatorname{LB}=c+\sum_{i\in R}\min_{j\in J:A_{ij}=1}w_{ij}. $$

If a remaining worker has no compatible available job, the state is infeasible. Otherwise every completion pays at least each row's minimum. Allowing two row minima to use the same job only relaxes the problem, so it keeps the bound valid, though potentially weak.

To find one optimal value or one optimal assignment, prune when $\operatorname{LB}\ge U$. To enumerate every optimal assignment, equality cannot be discarded without an additional tie-handling method: a branch with lower bound equal to the incumbent may contain another optimum. A heuristic score is not a safe bound unless its inequality is proved.

Exercise. Why does using the sum of remaining row maxima give an unsafe pruning rule for minimization? Hint: it overestimates rather than underestimates. Solution: a completion may choose cheap entries well below those maxima. Pruning because this overestimate exceeds the incumbent could remove a better solution. Upper bounds on completion costs do not serve as lower bounds for minimization.

38.3 Dynamic programming over combinatorial states

Optional extension; not required to complete the chapter foundation.

A bitmask represents a subset of jobs: bit $j$ is one exactly when job $j$ is used. Let $\operatorname{popcount}(S)$ be its number of set bits. Process masks in increasing integer order; adding an unset bit always increases the integer, so every transition goes to a later state. The empty state has count one, and every other state starts at zero.

Language-independent pseudocode. Allocate counts for all masks and initialize only the empty count to one. For each mask, set the next worker index to its population count. If all workers are assigned, skip transitions. Otherwise, for every compatible unused job, add the current count to the mask with that job included. Return the full-mask count. The induction invariant is that each stored count equals the number of valid prefixes onto that job set; unique last-step decomposition proves correctness.

The code also implements a streaming enumerator using a completion oracle. For each residual bipartite graph, the oracle tries to augment a matching once for each remaining worker. A failed augmenting-path search certifies no matching covering those workers; successful augmentation for all workers certifies extendability. This is a standard maximum-matching criterion from the graph and flow prerequisites. Each call costs $O(n^3)$ with the simple dense scans used here.

from itertools import permutations


def checked_matrix(matrix):
    rows = tuple(tuple(row) for row in matrix)
    n = len(rows)
    if any(len(row) != n for row in rows):
        raise ValueError("The compatibility matrix must be square")
    if any(type(value) not in (int, bool) or value not in (0, 1)
           for row in rows for value in row):
        raise ValueError("Entries must be binary integers or booleans")
    return rows


def count_assignments(matrix):
    rows = checked_matrix(matrix)
    n = len(rows)
    full = (1 << n) - 1
    counts = [0] * (1 << n)
    counts[0] = 1
    for mask in range(1 << n):
        ways = counts[mask]
        worker = mask.bit_count()
        if ways == 0 or worker == n:
            continue
        for job in range(n):
            bit = 1 << job
            if rows[worker][job] and not (mask & bit):
                counts[mask | bit] += ways
    return counts[full]


def enumerate_assignments(matrix):
    rows = checked_matrix(matrix)
    n = len(rows)
    prefix = []

    def extendable(first_worker, used):
        owner = [-1] * n

        def augment(worker, seen):
            for job in range(n):
                bit = 1 << job
                if used & bit or seen[job] or not rows[worker][job]:
                    continue
                seen[job] = True
                if owner[job] == -1 or augment(owner[job], seen):
                    owner[job] = worker
                    return True
            return False

        for worker in range(first_worker, n):
            if not augment(worker, [False] * n):
                return False
        return True

    def visit(worker, used):
        if worker == n:
            yield tuple(prefix)
            return
        for job in range(n):
            bit = 1 << job
            if rows[worker][job] and not (used & bit):
                next_used = used | bit
                if extendable(worker + 1, next_used):
                    prefix.append(job)
                    yield from visit(worker + 1, next_used)
                    prefix.pop()

    if extendable(0, 0):
        yield from visit(0, 0)


if __name__ == "__main__":
    example = [[1, 1, 0], [0, 1, 1], [1, 0, 1]]
    brute = [p for p in permutations(range(3))
             if all(example[i][p[i]] for i in range(3))]
    streamed = list(enumerate_assignments(example))
    assert count_assignments(example) == len(brute) == 2
    assert streamed == brute == [(0, 1, 2), (1, 2, 0)]
    assert count_assignments([]) == 1
    assert list(enumerate_assignments([])) == [()]
    print("count:", count_assignments(example))
    print("zero-based assignments:", streamed)

Solved output. The program prints count two and zero-based assignments $(0,1,2)$ and $(1,2,0)$, agreeing with enumeration of all six permutations. The counter uses $O(n2^n)$ arithmetic time and $O(2^n)$ count cells; integer bit costs follow the introduction's bound. The enumerator has a conservative $O(n^5)$ delay bound: between outputs it backtracks at most $n$ levels, considers at most $n$ candidates per level, and invokes an $O(n^3)$ oracle for each. It uses polynomial space and does not build the exponential completion table. The same bound covers finding the first output and finishing after the last; the initial oracle detects an empty output family in polynomial time.

The illustrative code uses recursion proportional to $n$, so a large instance may require an explicit stack to avoid interpreter recursion limits. The DP's exponential memory is another practical limitation. Turning the generator into a list for a large instance additionally stores all outputs and loses the streaming-space guarantee.

Exercise. Evaluate both functions on the $2\times2$ identity matrix and the zero matrix of that size. Hint: the empty assignment is the exceptional size-zero case only. Solution: the identity has count one and output $(0,1)$; the zero matrix has count zero and no outputs. These check forced choices and infeasibility without confusing them with empty input.

38.4 Subset DP, bitmasking, and meet-in-the-middle

Optional extension; not required to complete the chapter foundation.

Subset DP exploits equivalent histories; meet-in-the-middle instead balances two independent partial searches. For subset sum with integer weights $w_1,\ldots,w_n$ and target $T$, divide the indices into two parts. Enumerate each half's subset sums and search for a pair $a+b=T$. This uses about $2^{n/2}$ partial sums per balanced half instead of $2^n$ full subsets.

Solved example. With weights $(3,5,6,7)$ and target eleven, split into $(3,5)$ and $(6,7)$. Their sums are $0,3,5,8$ and $0,6,7,13$. The only complementary pair is $5+6=11$, giving the indexed subset containing the second and third weights. Checking the Cartesian product of both lists would still use $2^n$ work; sorting one list and using binary searches avoids that unnecessary full pairing.

With $M=2^{\lceil n/2\rceil}$, a straightforward implementation takes $O(nM)$ arithmetic and comparison work, including generation, sorting, and searches, and $O(M)$ sum records. For input integers of at most $b$ bits, subset sums need $O(b+\log(n+1))$ bits, and arithmetic and comparison costs must include that length. The method is not polynomial in $n$.

Keep indexed witnesses or multiplicities when counting. Equal sum values need not represent the same subset. For weights $(5,5)$ and target five, there are two indexed subsets, even though a deduplicated set of sum values contains five only once. Deduplication is safe for decision but would lose counting information.

Bitmask operations likewise need a stated model. The usual $O(1)$ bit-operation notation assumes masks fit in the machine word used by the implementation. Arbitrarily long masks require multiple words; the combinatorial state count remains $2^n$, but machine-level costs change.

Exercise. On the same four weights, solve target ten by the two lists. Hint: look for the complement of each left sum. Solution: $3+7=10$ is the unique complementary pair, giving the first and fourth weights. Neither a sum alone nor the empty subset is a second witness.

38.5 Fast subset transforms and subset convolution

Optional extension; not required to complete the chapter foundation.

For a function $f$ on subsets of an $n$-element universe, the subset zeta transform is $F(S)=\sum_{T\subseteq S}f(T)$. Directly visiting every pair $T\subseteq S$ costs $3^n$: each ground element is outside $S$, in $S\setminus T$, or in $T$. The fast transform starts with $F=f$ and processes one ground element at a time, adding $F(S\setminus\{i\})$ to $F(S)$ for masks containing $i$. After processing a coordinate set $B$, the value sums exactly over subsets obtainable by deleting elements of $B$. This invariant proves correctness in $O(n2^n)$ additions and $O(2^n)$ cells. Replacing additions by subtractions yields the Möbius inverse over a ring.

Solved example. In mask order $\varnothing,\{a\},\{b\},\{a,b\}$, take $f=(1,2,3,4)$. Processing $a$ gives $(1,3,3,7)$; processing $b$ gives $(1,3,4,10)$. Subtracting along the coordinates recovers the original vector. The total transform entry ten equals the sum of all four original entries.

Subset convolution is

$$ (f\star g)(S)=\sum_{T\subseteq S}f(T)g(S\setminus T). $$

Unlike ordinary transformed multiplication, it requires the two pieces to be disjoint. For $g=(5,6,7,8)$, direct convolution gives $(5,16,22,60)$. Its full-set value is $1\cdot8+2\cdot7+3\cdot6+4\cdot5=60$.

For fast convolution, separate by rank: let $f_i(T)=f(T)$ when $|T|=i$ and zero otherwise, and likewise $g_i$. Zeta-transform every rank. At each $S$, form $H_k(S)=\sum_{i=0}^kF_i(S)G_{k-i}(S)$, then Möbius-invert in the subset coordinate. The inverse retains pairs whose union is exactly $S$; taking rank $k=|S|$ additionally forces their intersection empty, since $|A|+|B|=|A\cup B|+|A\cap B|$. This gives the desired convolution in $O(n^22^n)$ ring operations and $O(n2^n)$ ring cells. See the primary algorithm of Björklund, Husfeldt, Kaski, and Koivisto, Fourier meets Möbius: fast subset convolution.

Exercise. Why is multiplying the ordinary zeta transforms and inverting insufficient in the worked example? Hint: it counts overlapping pairs as well. Solution: the pointwise products are $(5,33,48,260)$, and inversion gives $(5,28,43,184)$. The full-set value $184$ differs from $60$ because it includes pairs of subsets with nonempty overlap. Rank tracking removes those extra pairs. Möbius subtraction also means the ring algorithm cannot be transferred directly to arbitrary min-plus arithmetic without further machinery.

38.6 Inclusion-exclusion algorithms

Optional extension; not required to complete the chapter foundation.

The assignment count is the permanent of $A$:

$$ \operatorname{per}(A)=\sum_{\pi\in S_n}\prod_{i=1}^n A_{i,\pi(i)}. $$

Unlike the determinant, this formula has no permutation signs. Inclusion–exclusion replaces the sum over permutations by a sum over job subsets:

$$ \operatorname{per}(A)=\sum_{S\subseteq[n]}(-1)^{n-|S|} \prod_{i=1}^n\left(\sum_{j\in S}A_{ij}\right). $$

To prove it, expand the product as a sum over all functions from workers to jobs in $S$. A function with image $T$ receives total coefficient $\sum_{S\supseteq T}(-1)^{n-|S|}$, which is zero unless $T=[n]$, when it is one. A surjection between two $n$-element sets is a permutation. This is Ryser's formula, obtained directly from the inclusion–exclusion prerequisite; see Ryser's original treatment in Combinatorial Mathematics.

Solved example. For the motivating $3\times3$ matrix, the products of row sums are zero for the empty set and all three singleton subsets. Each two-job subset contributes product two with negative sign; the full set has product $2^3=8$ with positive sign. Thus the count is $8-2-2-2=2$. Individual positive and negative contributions need not represent disjoint families of valid assignments; cancellation removes the non-surjective functions.

Recomputing every row sum from scratch takes $O(n^22^n)$ arithmetic operations. Visiting subsets in Gray-code order changes one job at a time, so every row sum updates by adding or subtracting that column entry. Multiplying the $n$ updated row sums and adding the signed term then costs $O(n)$ per subset, for $O(n2^n)$ arithmetic operations. Working storage is $O(n)$ integer values beyond the matrix and subset-generation machinery, unlike the $O(2^n)$ DP table.

For binary input, terms are bounded by $n^n$ and intermediate accumulated magnitudes by $2^nn^n$, needing $O(n\log(n+1))$ bits. The arithmetic bound includes multiplications, which have their own bit complexity; it is not the same bit-cost calculation as the addition-only assignment DP. Exact signed arithmetic avoids numerical cancellation errors. For the size-zero matrix, use the empty-product convention one.

Exercise. Apply the formula to the all-ones $2\times2$ matrix. Hint: singleton row-sum products equal one. Solution: the empty term is zero, the two singleton terms are $-1$ each, and the full term is four. Their sum is two, agreeing with the two permutations.

38.7 Parameterized algorithms and fixed-parameter tractability

Optional extension; not required to complete the chapter foundation.

A parameterized algorithm is fixed-parameter tractable if its runtime is $f(k)N^c$, where $N$ is input size, $k$ is the parameter, and the exponent $c$ does not depend on $k$. A bound $N^k$ is generally an XP bound rather than an FPT bound. The distinction matters when a structural parameter is small but the graph is large.

For Vertex Cover, the input is a finite simple graph and a nonnegative budget $k$. A cover must contain at least one endpoint of every edge. On an uncovered edge $uv$, branch into taking $u$ or taking $v$, delete the chosen vertex and its incident edges, and decrease $k$ by one. An edgeless residual graph is successful; a residual edge with zero budget is a failure. Every cover contains one branch endpoint, proving completeness. The depth is at most $k$, giving at most $2^{k+1}-1$ search nodes and $O(2^k(n+m))$ time with straightforward graph scans.

Solved example. For the path $a-b-c-d$ with $k=2$, branch on $ab$. Taking $a$ leaves $bc,cd$; choosing $b$ next fails because $cd$ remains with no budget, while choosing $c$ succeeds with $\{a,c\}$. Taking $b$ leaves only $cd$; choosing $c$ or $d$ succeeds. The three size-two covers are $\{a,c\},\{b,c\},\{b,d\}$. No size-one cover exists because edges $ab$ and $cd$ are disjoint.

A simple kernel improves the residual input. If a vertex has degree greater than the remaining $k$, it must be in every budget-respecting cover: excluding it would require all its distinct neighbors. Apply this rule repeatedly, updating the budget, and remove isolated vertices. Reject if the budget becomes negative. When all degrees are at most $k$, more than $k^2$ remaining edges certifies failure, since $k$ selected vertices cover at most $k^2$ edges. Otherwise at most $2k^2$ nonisolated vertices remain. These rules preserve the decision answer; they are not automatically parsimonious transformations for counting all covers.

Exercise. Solve a star with five leaves at budget one using the forcing rule. Hint: the center's degree exceeds the budget. Solution: the center must be chosen; deleting it leaves no edges and zero budget, so the instance is feasible. Choosing any leaf alone would leave four edges uncovered.

38.8 Tree decompositions and treewidth-based algorithms

Optional extension; not required to complete the chapter foundation.

A tree decomposition assigns a bag $B_t$ of vertices to each node of a tree. Every graph vertex appears in some bag, every edge has both endpoints in some bag, and the bags containing a particular vertex form a connected subtree. Its width is $\max_t|B_t|-1$; treewidth is the minimum width. The connected-subtree condition makes bag vertices a valid interface between already processed and unprocessed graph portions.

For counting independent sets, a state records which bag vertices are selected. Selected vertices within a bag must be independent. In a rooted nice decomposition, introduce operations add a vertex with compatible selection status; forget operations sum the states where that vertex is absent or present; join operations multiply child counts with the same bag state. The children share only the bag in the relevant processed regions, and there are no edges between their interiors. Therefore matching bag states makes the combination unique and valid.

Given such a decomposition of width $w$ with $N_T$ nodes, this yields $O(2^{w+1}\operatorname{poly}(w)N_T)$ arithmetic operations. Storing all node tables uses $O(2^{w+1}N_T)$ integer cells. Counts are at most $2^n$, so their bit lengths are $O(n)$; arithmetic and storage claims must account for that if stated in bits. Obtaining a suitable decomposition is a separate task; this bound assumes it is supplied, not that optimal treewidth is free to compute.

Solved example. The path $a-b-c-d$ has bags $\{a,b\},\{b,c\},\{c,d\}$ linked in that order, giving width one. Each vertex's occurrences are connected and every edge is covered. A path-specialized DP uses $F_i(0)$ and $F_i(1)$, the counts on the first $i$ vertices with the last vertex excluded or included:

$$ F_i(0)=F_{i-1}(0)+F_{i-1}(1),\qquad F_i(1)=F_{i-1}(0). $$

Initialize $(F_0(0),F_0(1))=(1,0)$. Successive pairs are $(1,1),(2,1),(3,2),(5,3)$, so the path has eight independent sets. They are the empty set, four singletons, and $\{a,c\},\{a,d\},\{b,d\}$. This explicitly verifies the interface recurrence.

Exercise. Why are the two bags $\{a,b\}$ and $\{c,d\}$ insufficient for this path? Hint: check the middle edge. Solution: edge $bc$ has no bag containing both endpoints, violating edge coverage. A decomposition cannot omit a constraint merely to make its bags small.

38.9 Exact exponential algorithms

Optional extension; not required to complete the chapter foundation.

The notation $O^{\ast}(c^n)$ suppresses polynomial factors, not the exponential factor. Exact exponential analysis tries to reduce the base using a proved recurrence, rather than claiming that typical pruning makes the worst case small. Polynomial working space and running time are separate measures.

For Maximum Independent Set, branch on a vertex $v$. Excluding it leaves $G-v$; including it forces deletion of its closed neighborhood $N[v]$ and adds one to the optimum. Thus

$$ \alpha(G)=\max\{\alpha(G-v),\ 1+\alpha(G-N[v])\}. $$

An isolated vertex is always included in some optimum and can be removed while adding one. If a leaf $u$ has neighbor $v$, some maximum independent set contains $u$: an optimum containing $v$ can replace it by $u$, and an optimum containing neither can add $u$. Therefore $\alpha(G)=1+\alpha(G-N[u])$ for a leaf. This reduction preserves the optimum value but may discard other optimal sets, so it is not a complete enumeration rule.

After these reductions, every residual vertex has degree at least two. Branching on any vertex removes at least one vertex in the exclusion branch and at least three in the inclusion branch. Consequently the branching recurrence is bounded by $T(n)\le T(n-1)+T(n-3)$, up to polynomial processing costs. Its characteristic equation is $c^3=c^2+1$, whose positive root is about $1.4656$. A safe stated bound is $O^{\ast}(1.466^n)$ with polynomial space for depth-first recursion. This is an elementary derived bound, not a claim of a best published algorithm.

Solved example. On $C_4$, choose vertex $a$. Including it removes $a$ and its two neighbors, leaving the opposite isolated vertex, so the branch obtains an independent set of size two. Excluding $a$ leaves a three-vertex path, whose leaf reduction also gives size two. Thus $\alpha(C_4)=2$. The two maximum sets are the opposite pairs; a value-preserving leaf reduction need not list both in every branch.

Exercise. Why is it unsafe to use $T(n)\le T(n-1)+T(n-3)$ before handling leaves? Hint: a leaf's closed neighborhood has only two vertices. Solution: branching on a degree-one vertex removes only two vertices in the inclusion branch, yielding $T(n-1)+T(n-2)$ instead. The stronger recurrence depends on the proved preprocessing guarantee of residual minimum degree at least two.

38.10 Enumeration complexity and polynomial-delay algorithms

Optional extension; not required to complete the chapter foundation.

An output-polynomial algorithm finishes in time polynomial in the input size plus the total encoded output size. A polynomial-delay algorithm additionally bounds the time before the first output, between successive outputs, and after the final output by a polynomial in input size. Thus a long initial computation cannot be hidden just because the output family is enormous. Delay includes writing one output, whose size must itself be bounded appropriately.

Reachability pruning does not guarantee polynomial delay. A partial assignment may be locally valid but have no completion; exploring a large tree of such prefixes can create a long output gap. The assignment enumerator instead uses a polynomial-time extendability oracle, deleting entire dead subtrees before entering them.

Solved example and proof. On the motivating matrix, after outputting $(1,2,3)$, the search considers prefix $(1,3)$. Its residual graph has worker three and job two with no edge, so the matching oracle rejects it. The next feasible prefix begins $(2,3)$ and leads to $(2,3,1)$. In general, every accepted prefix has at least one output descendant. A depth-first traversal between two leaves climbs at most $n$ levels and then descends at most $n$ levels. At a visited level, at most $n$ candidate jobs are tested before an accepted branch or exhaustion. Therefore at most $O(n^2)$ completion tests occur in a gap. With the $O(n^3)$ oracle, the delay is $O(n^5)$, deliberately coarse but polynomial.

The root oracle handles zero-output inputs, and the same ascent bound handles final termination. Prefixes are output in a fixed worker order with jobs considered in increasing order, so the stream is lexicographic and duplicate-free. The mutable prefix and the matching oracle use polynomial working space; no list of previously output assignments is stored.

An exponential completion DP can also guide enumeration, giving short gaps after its table is built. But its $O(n2^n)$ preprocessing violates the standard polynomial-delay requirement unless that startup cost is explicitly allowed in a different performance contract. Decision by bipartite matching is polynomial even though the assignment-counting DP and explicit enumeration can require exponential total work. Polynomial delay does not imply polynomial total time when there are $n!$ outputs.

Exercise. Is “build an exponential table, then emit every solution with constant computational overhead” a polynomial-delay guarantee? Hint: include startup and output-writing time. Solution: not under the definition used here, because first-output delay is exponential. Also each assignment has $n$ indices and takes at least its encoded length to write. A valid report must state preprocessing separately and include the output cost.

Design an exact algorithm with a proof and an honest complexity bound

The investigation designs exact assignment counting and streaming enumeration from the same combinatorial input. It connects recursive search to state compression and to the stronger completion tests needed for delay guarantees. The supplied code is a reference implementation to test against independent brute force, not a substitute for a proof.

Worked solution: exhaustive trace and states. In one-based notation, the permutations are $(1,2,3),(1,3,2),(2,1,3),(2,3,1),(3,1,2),(3,2,1)$. The first and fourth are valid. The others respectively fail at worker three, worker two, worker one, and worker one. The subset-state counts, ordered as $\varnothing,\{1\},\{2\},\{3\},\{1,2\},\{1,3\},\{2,3\},\{1,2,3\}$, are $1,1,1,0,1,1,1,2$. Prefix $(1,3)$ is reachable but not extendable.

Worked solution: counting proof and resources. Initialize the empty prefix count to one. For a nonempty $S$, the last worker chooses exactly one job $j\in S$; removing that choice gives a unique valid prefix on $S\setminus\{j\}$. Conversely every predecessor combined with a permitted final edge gives one valid new assignment. This bijection proves the recurrence by induction on $|S|$. Increasing mask order is valid because a transition adding a bit increases the integer mask. The full mask counts exactly all compatible bijections.

There are $2^n$ states and $n2^{n-1}$ pairs $(S,j)$ with $j\notin S$, so forward transition candidates have that count before compatibility filtering. The code scans all $n$ job indices at each processed mask, yielding the stated $O(n2^n)$ arithmetic bound. Counts use at most $B=O(n\log(n+1))$ bits. A safe bit-time bound is $O(n2^nB)$ when additions and $n$-bit mask operations have linear cost in their bit lengths, with $O(2^nB+n^2)$ bit storage and polynomial input validation additional. The size-zero case is handled explicitly by count one and the unique empty tuple.

Worked solution: enumeration proof. Fixing a prefix deletes its already assigned workers and used jobs. A completion is precisely a perfect matching of the residual bipartite graph: every remaining worker is matched once and all remaining jobs are distinct. There are equally many remaining workers and jobs, so a matching covering the workers also covers the jobs. The augmenting-path oracle tests this condition exactly.

Only extendable branches are entered, so every explored prefix lies on an output path. Every compatible complete permutation remains reachable because its residual restrictions admit its own completion. The fixed assignment order gives one path per output. Between outputs, or during startup or termination, at most a constant multiple of $n$ levels are climbed or descended, with at most $n$ candidate tests at each. Combining $O(n^2)$ tests with $O(n^3)$ per oracle gives $O(n^5)$ delay for positive $n$, and the empty case has constant behavior. Dense input and the search/oracle arrays use polynomial space. Replacing the oracle by a precomputed exponential table changes startup to exponential even if subsequent gaps are small.

Worked solution: finite validation. The test range contains

$$ 2^{0^2}+2^{1^2}+2^{2^2}+2^{3^2}=1+2+16+512=531 $$

binary matrices. For each, generate permutations independently, filter them by the matrix, and compare both functions' results with that list. Include the empty matrix, all-zero matrices, identity matrices, and all-ones matrices. Also reject a nonsquare matrix and entries outside the binary integer/Boolean domain. Agreement on all 531 inputs is a strong finite check; it does not replace the all-size proof. Performance measurements should record the method, input family, preprocessing, and output count rather than reporting a single runtime as a universal guarantee.

Application and optional extension. Compatible assignments model assigning staff to roles, instruments to experiments, or exclusive resources to tasks. The binary model assumes one worker per job and one job per worker; capacities, fairness, scheduling conflicts, or skill bundles introduce additional constraints. The polynomial matching oracle supports prompt enumeration of feasible alternatives in this model, while exact counts quantify how many alternatives exist. Storing every alternative can still require factorial space even though the generator's working storage is polynomial.

For minimum costs, replace counts by best prefix costs: initialize $C(\varnothing)=0$ and all other entries to infinity, and update $C(S\cup\{j\})$ with the minimum of its current value and $C(S)+w_{|S|,j}$ over permitted unused jobs. Unique prefix decomposition proves the optimal-substructure recurrence. Store a predecessor to recover one optimum. Recovering all optima requires retaining or reconstructing all equality-achieving choices; a branch-and-bound rule that discards equality would lose them. The state-space bound remains exponential, and cost arithmetic must include the bit length of the input weights.