TAOCP 7.2.1.3 Exercise 13

Section 7.2.1.3: Generating All Combinations

Exercise 13. [25] [25] A one-dimensional Ising configuration of length n, weight t, and energy r, is a binary string an−1 . . . a0 such that n−1 j=0 aj = t and n−1 j=1 bj = r, where bj =

7.2.1.3 GENERATING ALL COMBINATIONS 381 aj ⊕aj−1. For example, a12 . . . a0 = 1100100100011 has weight 6 and energy 6, since b12 . . . b1 = 010110110010. Design an algorithm to generate all such configurations, given n, t, and r.

Verified: no
Solve time: 6m27s

Let $\alpha$ be the $t$-combination $c_t \cdots c_1$ with $n > c_t > \cdots > c_1 \ge 0$, viewed as the $t$-element set ${c_1,\dots,c_t} \subseteq {0,1,\dots,n-1}$. The operator $\partial_t$ produces all $(t-1)$-combinations obtained by deleting exactly one element of $\alpha$, hence

$$ \partial_t \alpha = {, \alpha \setminus {c_j} : 1 \le j \le t ,}. $$

The operator $\partial_{t+1}$ produces all $(t+1)$-combinations that contain $\alpha$, hence all supersets obtained by adjoining one new element from the complement of $\alpha$ in ${0,1,\dots,n-1}$. Writing $U = {0,1,\dots,n-1}$, this gives

$$ \partial_{t+1} \alpha = {, \alpha \cup {k} : k \in U \setminus \alpha ,}. $$