 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\mathrm{XOR}\lfloor i/2\rfloor$ for $0\le 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 $n{2}^n$ bit writes, even if the generation state changes only once per object. Useful performance measures therefore distinguish initialization, delay between objects, working memory and the unavoidable output size.