Efficient Coroutine Generation of Constrained Gray Sequences
(originally entitled "Deconstructing Coroutines")

Donald E. Knuth, Department of Computer Science, Stanford University, USA.
Frank Ruskey, Department of Computer Science, University of Victoria, Canada.


We study an interesting family of cooperating coroutines, which is able to generate all patterns of bits that satisfy certain fairly general ordering constraints, changing only one bit at a time. (More precisely, the directed graph of constraints is required to be cycle-free when it is regarded as an undirected graph.) If the coroutines are implemented carefully, they yield an algorithm that needs only a bounded amount of computation per bit change, thereby solving an open problem in the field of combinatorial pattern generation.

Back to list of publications.