= Combinatorial generation
<Combinatorial generation> enumerates finite objects satisfying a specified structure, such as <permutations>, <subsets> or <set partitions>. A generation procedure must explain both completeness, meaning every required object appears, and uniqueness, meaning objects are not emitted twice under the chosen equivalence convention. Counting the objects is a different task from writing them all down.
For all length-three binary <strings>, a <Gray code> order is `000,001,011,010,110,111,101,100`. Consecutive <strings> differ in exactly one <bit>. More generally, the reflected binary <Gray code> is $g(i)=i\mathbin{\mathrm{XOR}}\lfloor i/2\rfloor$ for $0\leq i<2^n$, using <bitwise exclusive or>. Its map is invertible: recover each binary digit of $i$ by accumulating the <exclusive or> of the higher <Gray code> digits. Thus all $2^n$ objects occur exactly once.
A one-bit update can be cheap while reporting a whole object is expensive. Writing every length-$n$ binary <string> explicitly takes at least $n2^n$ <bit>[bit writes], even if the generation state changes only once per object. Useful performance measures therefore distinguish initialization, delay between objects, <space complexity>[working memory] and the unavoidable <output> size.
Back to article page
