Chapter 5: Algorithmic Generation of Combinatorial Structures

Can Every Subset Be Visited by Changing One Bit?

Suppose a system has three optional features. A configuration is a subset of these features, or equivalently a 3-bit binary word: a $1$ means a feature is enabled, and a $0$ means it is disabled. There are $2^3 = 8$ total configurations.

Ordinary binary counting visits all eight configurations in numerical sequence ($000 \to 001 \to 010 \to 011 \to \dots$), but the transition from $011$ to $100$ flips all three bits simultaneously. In physical hardware, sensors, and state machines, multi-bit transitions cause glitching, power spikes, and timing race conditions. Can we visit every configuration exactly once while changing only one feature at a time?

This chapter explores algorithmic generation across four foundational tasks:

5.1 Generating Permutations and Inversions

A permutation of $n$ distinct symbols is an ordered arrangement of those symbols. For $\{1, 2, 3\}$, the six permutations listed in standard dictionary (lexicographic) order are:

Lexicographic order compares two sequences at their first differing position from left to right. Whichever sequence possesses the smaller symbol at that position appears first.

Worked example (0-based indexing). Starting with $A=[1,3,5,4,2]$, scan from the right to find the last ascent: $A[1]=3 < A[2]=5$, so the pivot is $i=1$. The suffix $[5,4,2]$ is decreasing. Scanning it from the right, the first value greater than $3$ is $A[3]=4$, so $j=3$. Swap the pivot and target to get $[1,4,5,3,2]$, then reverse the suffix after index $1$, $[5,3,2]$, to obtain the successor $[1,4,2,3,5]$.

Why is this the exact immediate successor? The suffix following the rightmost pivot $i$ is strictly decreasing, making it the maximum possible arrangement of those specific symbols. Any larger permutation must alter the pivot or an earlier position. Replacing $a_i$ with the smallest strictly larger symbol in the suffix makes the increase minimal. Reversing the suffix afterwards turns it from strictly decreasing to strictly increasing, producing the smallest possible prefix extension. In inversion terms, this changes the suffix from having all $\binom{m}{2}$ possible internal inversions (where $m$ is its length) to having none; this local change helps minimize the successor's remaining suffix.

Last permutation. If no pivot exists, the whole sequence is decreasing, which is the final permutation in lexicographic order. For example, reversing $[5,4,3,2,1]$ returns the first permutation $[1,2,3,4,5]$ when generation is meant to cycle.

Inversions and Minimum Adjacent Swaps

An inversion of a permutation $\pi = (\pi_1, \pi_2, \dots, \pi_n)$ is an out-of-order pair of positions $(i, j)$ where $i < j$ but $\pi_i > \pi_j$. The total number of inversions is denoted $\operatorname{inv}(\pi)$.

In simple terms: an inversion is a pair of values that appears in the wrong order: the larger value comes first. In an increasing list such as $(1,2,3,4)$, there are no inversions. To check a pair, look at their order in the permutation: if $x$ appears before $y$ and $x>y$, that pair is an inversion.

Concrete example. For $\pi=(3,1,4,2)$, compare each pair from left to right:

• $3$ appears before $1$, and $3>1$: inversion $(3,1)$.
• $3$ appears before $4$, but $3<4$: not an inversion.
• $3$ appears before $2$, and $3>2$: inversion $(3,2)$.
• $1$ appears before $4$ and before $2$, and is smaller than both: neither pair is an inversion.
• $4$ appears before $2$, and $4>2$: inversion $(4,2)$.

Thus the inversion pairs are $(3,1)$, $(3,2)$, and $(4,2)$, so $\operatorname{inv}(\pi)=3$.

A direct inversion counter checks all $\binom{n}{2}$ position pairs in $O(n^2)$ time. The count ranges from $0$ for the increasing permutation to $\binom{n}{2}=\frac{n(n-1)}{2}$ for the decreasing permutation: there are $\binom{n}{2}$ pairs in total, and in descending order every pair is inverted. Swapping an adjacent inverted pair reduces $\operatorname{inv}(\pi)$ by exactly one without affecting any other pairwise relationships. Repeating such swaps sorts the sequence, so the inversion count is exactly the minimum number of adjacent swaps needed to sort it; Bubble Sort, for example, performs that many swaps when it swaps adjacent out-of-order elements until sorted.

Inversion count and lexicographic order describe different things. For $n=3$, the lexicographic list has inversion counts $0,1,1,2,2,3$ for $(1,2,3),(1,3,2),(2,1,3),(2,3,1),(3,1,2),(3,2,1)$. The endpoints are always the increasing permutation with zero inversions and the decreasing permutation with the maximum, but the count does not generally increase at every lexicographic step: for $n=4$, $(1,4,3,2)$ has $3$ inversions and its lexicographic successor $(2,1,3,4)$ has only $1$.

Connection to the immediate successor. Narayana's next-permutation algorithm (described above) finds the rightmost ascent, swaps its pivot with the smallest larger value to its right, then reverses the suffix. That suffix is initially decreasing, so a suffix of length $m$ has all $\binom{m}{2}$ possible internal inversions; after reversal it is increasing and has none. For the earlier example, the suffix $[5,3,2]$ after the swap has $3$ internal inversions, while $[2,3,5]$ after reversal has $0$. This reversal makes the tail as small as possible after the pivot is increased, which is why the result is the immediate lexicographic successor. It does not mean inversion counts always rise as we advance lexicographically—the $n=4$ counterexample above shows they can fall.

5.2 Generating combinations and subsets

Represent a $k$-element subset of $\{0,1,\ldots,n-1\}$ by its increasing tuple

$$ 0\le c_1\lt c_2\lt\cdots\lt c_k\le n-1. $$

Increasing tuples remove duplicates caused by different orders of the same selected elements. For $1\le k\le n$, the first tuple is $(0,1,\ldots,k-1)$ and the last is $(n-k,n-k+1,\ldots,n-1)$.

To find the next tuple in lexicographic order, scan from right to left for the largest index $i$ satisfying

$$ c_i\lt n-k+i-1. $$

Increment $c_i$ by one. Then reset every later coordinate to the smallest possible value: $c_{i+1}=c_i+1$, $c_{i+2}=c_i+2$, and so on. If no coordinate can increase, stop.

The upper bound on $c_i$ reserves enough larger elements for the remaining $k-i$ positions. Choosing the rightmost movable coordinate keeps the longest possible prefix unchanged. Resetting the suffix to its minimum produces the immediate successor, so the generator is complete and has no duplicates.

For $k=0$, there is one combination, the empty tuple. If $k\gt n$ or $k\lt0$, there are no combinations. These cases should be handled before attempting to scan tuple positions.

All subsets. A subset can also be represented by an $n$-bit membership word. Enumerating every binary word lists all $2^n$ subsets. Alternatively, generate combinations separately for sizes $k=0,1,\ldots,n$; these classes are disjoint and contain $\sum_k\binom nk=2^n$ objects altogether.

Scanning and resetting the tuple takes $O(k)$ time in the worst case per successor, with $O(1)$ auxiliary space beyond the tuple. Copying an output requires $O(k)$ time. These bounds describe this straightforward generator; they do not assert that every transition needs to change all coordinates.

5.3 Lexicographic and Gray-code Orderings

For fixed-length binary words of length $n$, lexicographic order (using $0 < 1$) matches ordinary binary numerical order. For length $n = 3$, counting in lexicographic order yields: $000, 001, 010, 011, 100, 101, 110, 111$. However, a Gray code ordering visits the exact same set of $2^n$ binary words in a sequence where every adjacent pair differs by only a single bit.

The total number of differing bit positions between two binary words $a$ and $b$ is called their Hamming distance, denoted $H(a, b)$. While lexicographic order suffers from jumps with Hamming distances up to $n$ (such as $011 \to 100$ where $H(011, 100) = 3$), a Gray code guarantees $H(g_i, g_{i+1}) = 1$ for all steps $i$.

Building $G_3$ from $G_2$. Keep $G_2=(00,01,11,10)$ in its original order for the first half and prefix each word with $0$: $(000,001,011,010)$. Reverse $G_2$ to get $(10,11,01,00)$, prefix each word with $1$ for the reflected half $(110,111,101,100)$, then concatenate:

For instance, the middle transition is $010\to110$: the two words share the same tail $10$, so only the new leading bit changes.

Why does reflection guarantee Hamming distance $1$? The construction preserves the one-bit-change property inside each half and makes the join between the halves differ in only the leading bit:

• Base case: $G_1=(0,1)$ contains both one-bit words, and the only transition changes one bit.
• Completeness and uniqueness: The first half contains every $(n-1)$-bit word prefixed by $0$ exactly once. The second contains every such word prefixed by $1$ exactly once. The halves cannot overlap because their first bits differ, so together they contain all $2^n$ words.
• Inside either half: The prefixed bit is constant, so it contributes no difference between neighboring words. The remaining bits follow $G_{n-1}$ or the same sequence in reverse; reversing order does not change the Hamming distance of neighboring pairs.
• At the join: The last word of the first half is $0+\operatorname{last}(G_{n-1})$. Since the second half uses the reversed list, its first word is $1+\operatorname{last}(G_{n-1})$. Their tails match exactly, so only the leading bit changes.
• Wrap-around (cyclic version): The first word is $0+\operatorname{first}(G_{n-1})=0^n$. The last word is $1+\operatorname{first}(G_{n-1})=10^{n-1}$, because reflection puts the original first word last. These differ only in the leading bit, so the last and first words also have Hamming distance $1$.

Direct Closed-Form Computation: $g(i) = i \oplus \lfloor i / 2 \rfloor$

Instead of recursively constructing previous lists, we can compute the Gray code word at step $i$ ($0 \le i < 2^n$) directly in $O(1)$ time using bitwise operations:

where $\oplus$ represents the bitwise exclusive OR (XOR) operation, which outputs 1 wherever two input bits differ and 0 where they match. Dividing by 2 is equivalent to a logical right shift by 1 bit.

Invertibility (Unranking Gray Codes): To recover index $i$ from a Gray code word $g$, start with the most significant bit (MSB) equal to $g$, and compute each subsequent bit as $i_k = i_{k+1} \mathbin{\oplus} g_k$. Because this mapping is bijective, all $2^n$ outputs are distinct.

Algebraic Proof of 1-Bit Adjacency: Suppose integer $i$ has $t$ trailing ones in binary. Incrementing $i$ to $i+1$ flips those $t$ trailing ones and the first preceding zero bit, giving $i \mathbin{\oplus} (i+1) = 2^{t+1} - 1$. Taking XOR with right shifts gives:

Since $2^t$ contains exactly one set bit at position $t$, $g(i)$ and $g(i+1)$ differ in exactly one bit position!

Language-Independent Generator Pseudocode: Validate that $n \ge 0$. For each integer $i$ from $0$ through $2^n-1$, choose $i$ itself for lexicographic order or $i \mathbin{\oplus} \lfloor i/2 \rfloor$ for Gray order. Format the integer as an $n$-digit binary string with leading zeros and emit it.

def binary_words(n, gray=False):
    if not isinstance(n, int) or n < 0:
        raise ValueError("n must be a nonnegative integer")
    if n == 0:
        yield ""
        return
    for i in range(1 << n):
        value = i ^ (i >> 1) if gray else i
        yield format(value, f"0{n}b")


def hamming_distance(a, b):
    if len(a) != len(b):
        raise ValueError("words must have equal lengths")
    return sum(x != y for x, y in zip(a, b))


if __name__ == "__main__":
    lex = list(binary_words(3))
    gray = list(binary_words(3, gray=True))
    assert lex == ["000", "001", "010", "011",
                   "100", "101", "110", "111"]
    assert gray == ["000", "001", "011", "010",
                    "110", "111", "101", "100"]
    assert len(set(gray)) == 8
    assert set(gray) == set(lex)
    assert all(hamming_distance(a, b) == 1
               for a, b in zip(gray, gray[1:]))
    assert hamming_distance(gray[-1], gray[0]) == 1
    assert list(binary_words(0, gray=True)) == [""]
    print("Lex:", " ".join(lex))
    print("Gray:", " ".join(gray))

Complexity & Storage Analysis: Because emitting full string representations takes $O(n)$ time per word, generating all $2^n$ binary words takes $O(n 2^n)$ total time and $O(n)$ auxiliary working space. Converting the generator to an explicit array costs $O(n 2^n)$ memory.

5.4 Backtracking and Recursive Generation

Backtracking is a systematic strategy for searching through a space of possibilities by constructing candidate objects one choice at a time. Think of it as exploring a maze: you follow a path as far as possible, and whenever you reach a dead end or a complete solution, you backtrack—stepping back to the most recent decision point to try a different path.

In a backtracking algorithm, the space of all partial solutions forms a search tree (or state-space tree):

• The root represents the initial empty state.
• An internal node represents a valid partial construction (a prefix).
• A leaf node represents a fully constructed complete object (or a dead end).
• Edges represent making a single valid decision to extend the current state.

Generating Permutations via Search Trees

To generate all $n!$ permutations of $\{1, 2, \dots, n\}$, we maintain a growing prefix list and a set of unused symbols:

• At the root node, the prefix is empty (), and all $n$ symbols are unused.
• At depth $k$, we try appending each remaining unused symbol in turn.
• When the unused set becomes empty (depth $n$), the current prefix is a valid leaf permutation and is emitted.
• When trying choices at each node in increasing numeric order, the leaves are emitted in exact lexicographic order!

Correctness Invariant: The prefix contains distinct elements, and the unused set contains exactly the symbols not in the prefix. Each permutation corresponds to a unique root-to-leaf path. Because every unused symbol is systematically attempted at each node, no valid permutation is skipped, and no permutation is generated twice.

Pruning Search Trees: Constrained Backtracking

Backtracking becomes exceptionally powerful when combined with pruning. Instead of generating a full candidate object and checking its validity at the end, pruning checks constraint feasibility at every internal node. If a partial prefix violates a rule, the algorithm prunes (cuts off) that entire sub-tree immediately!

Consider generating binary words of length $n = 3$ with no adjacent ones (no 11 allowed):

• At any node, we can always safely append 0.
• We can append 1 only if the current prefix is empty or its last digit is 0.
• If a prefix ends in 1, attempting to append 1 creates the illegal substring 11. We reject this branch immediately without exploring its children!

Complexity & Performance Analysis:

• For the "no adjacent ones" problem, the number of valid prefixes at successive lengths follows the Fibonacci recurrence $F_{n+2}$ from Chapter 4.
• Because invalid branches are pruned in $O(1)$ time upon creation, the total number of visited internal tree nodes is strictly within a constant factor of the number of valid emitted outputs $M$.
• Thus, internal traversal takes $O(M)$ operations for $M$ valid outputs (Constant Amortized Time per object).
• Working memory is limited to the single mutable prefix stack and recursion call stack of depth $O(n)$.

5.5 Ranking and Unranking Combinatorial Objects

When working with a collection of $M$ combinatorial objects (such as all $n!$ permutations or all $\binom{n}{k}$ subsets), it is often necessary to map each object to a unique integer index, and vice versa. This bridge between abstract structures and simple integers is defined by two complementary operations:

• Ranking: Converts a specific combinatorial object into its unique zero-based position index $R \in \{0, 1, \ldots, M-1\}$ within a specified ordering.
• Unranking: Reconstructs the exact combinatorial object corresponding to a given integer index $R \in \{0, 1, \ldots, M-1\}$.

Permutation Ranking and the Lehmer Code

Fix the symbol set $\{0, 1, \ldots, n-1\}$ in standard lexicographic order. At each position $i$ (from left to right) of a permutation $\pi$, let $d_i$ denote the number of currently unused symbols that are strictly smaller than the symbol chosen at position $i$. Equivalently, $d_i$ is the number of smaller elements located to the right of position $i$ in the permutation.

The sequence $(d_1, d_2, \ldots, d_n)$ is called the Lehmer code of the permutation. Each digit $d_i$ satisfies $0 \le d_i \le n-i$. Furthermore, the sum of these digits equals the total inversion count of the permutation: $\operatorname{inv}(\pi) = \sum_{i=1}^n d_i$.

Using the Lehmer code, the exact lexicographic rank of permutation $\pi$ is given by:

Why does this formula work? At position $i$, choosing a symbol that has $d_i$ smaller available candidates skips exactly $d_i$ blocks of permutations, where each block contains $(n-i)!$ permutations sharing the same prefix. Summing all skipped blocks yields the exact number of permutations preceding $\pi$.

The Factorial Unranking Procedure

To reverse the process and reconstruct the permutation at rank $R$ ($0 \le R < n!$), we maintain a sorted list of remaining unused symbols. At position $i$, we divide the current residual rank by $(n-i)!$:

• The quotient gives the zero-based index of the symbol to select from the unused list.
• The remainder becomes the new residual rank for the next position.

5.6 Combinatorial Number Systems

For fixed-size combinations ($k$-subsets of $\{0, 1, \dots, n-1\}$), ranking relies on binomial coefficients using colexicographic order (colex), rather than standard lexicographic order.

In colex order, two distinct $k$-subsets are compared by inspecting their largest differing element. Whichever subset contains the larger differing element comes later in colex order.

Greedy Unranking Algorithm: To find the $k$-subset matching rank $R$, search backwards from $j = k$ down to $1$. At each position $j$, find the largest integer $a_j$ such that $\binom{a_j}{j} \le R$. Subtract $\binom{a_j}{j}$ from $R$, and repeat for $j-1$ with upper bound $a_j-1$.

5.7 Constant-Amortized-Time (CAT) Generation

In combinatorial generation, an algorithm is said to run in Constant Amortized Time (CAT) per object if its total internal operations to generate $M$ objects is bounded by $O(M)$. This implies that the average work per generated object is $O(1)$, even if occasional individual transition steps take significantly longer.

Consider an $n$-bit binary counter visiting all $2^n$ configurations from $000 \dots 0$ to $111 \dots 1$. To increment the counter, we scan from the rightmost bit (LSB), turning trailing 1s into 0s, until we flip the first 0 to 1.

Proof of Constant Amortized Complexity: Numbering bits from right to left as $j = 1, 2, \dots, n$, bit position $j$ flips exactly $2^{n-j+1} - 1$ times across the full counting sequence. Summing across all $n$ positions:

Because the total work across all $2^n$ outputs is strictly less than $2 \cdot 2^n$, the average internal work per state transition is less than 2 bit flips—proving $O(1)$ constant amortized time!

5.8 Uniform Random Sampling of Finite Structures

Uniform sampling selects an object from a finite set of size $M$ such that every object has an identical probability $p = 1/M$ of being chosen.

1. Sampling via Unranking: Draw a random integer $R$ uniformly from $\{0, 1, \dots, M-1\}$, then return $\operatorname{unrank}(R)$. Because unranking is a bijection, every object corresponds to exactly one rank, guaranteeing exact uniform probability $1/M$ in $O(1)$ sampling time without generating preceding objects!

2. Exact Rejection Sampling (Avoiding Modulo Bias): Naively computing random_int() % M introduces probability bias if the random generator range is not a perfect multiple of $M$. To sample uniformly without bias, select the smallest power of two $2^b \ge M$, generate a $b$-bit integer, and reject any value $\ge M$, repeating until a valid integer $< M$ is accepted.

Direct Permutation Sampling: The Fisher–Yates Shuffle

Rather than converting huge ranks, the Fisher–Yates shuffle generates a uniformly random permutation in $O(n)$ time using in-place swaps:

1. Start with an array initialized to sorted order $(0, 1, \dots, n-1)$.
2. For index $i$ running from $n-1$ down to $1$:
   • Pick a uniform random integer $j$ from $\{0, 1, \dots, i\}$.
   • Swap elements at position $i$ and position $j$.

Proof of Uniformity: At step $i$, position $i$ receives a uniformly chosen element from the $i+1$ remaining candidates with probability $1/(i+1)$. Multiplying probabilities across all steps gives:

Build and verify a rank–unrank round trip

Generation provides an independent list against which a ranking system can be checked. Ranking supplies an exact index, and unranking supplies direct access to an object. Once the two maps are proved inverse, a uniform random index becomes a uniform random object.

Permutation inversion counts add another useful consistency check. The Lehmer digits used to compute a rank must sum to the inversion count obtained by testing position pairs. This connects permutation generation, ranking, and sampling without assuming that inversion counts themselves are uniformly distributed.

One application is testing a scheduler on all small orderings of distinct tasks, then sampling larger orderings when exhaustive testing becomes impractical. A stored rank identifies the chosen ordering exactly under a fixed symbol order and ranking convention. Uniform sampling covers permutations fairly, but it does not guarantee equal coverage of properties such as inversion count, execution time, or resource demand.