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.
Abstract:
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.
-
The compressed postscript file is
106,077 bytes.
-
The postscript file is 312,586 bytes.
-
Appears in From Object-Orientation to Formal Methods:
Dedicated to The Memory of Ole-Johan Dahl,
Lecture Notes in Computer Science 2635, Springer-Verlag, 2003, pp. 183-208.
-
This paper is Chapter 25 (pages 245-274)
in a volume of Don's collected papers entitled
Selected Papers on Computer Languages.
See
http://csli-publications.stanford.edu/site/1575863820.html
or
http://www-cs-faculty.stanford.edu/~knuth/cl.html
for further information.
-
The Gray code in this paper was first presented at the S.E. Conference
on Combinatorics, Graph Theory, and Computing in 1995. Some slides
from that talk are reproduced here.
-
Don has given some talks on the topic (details from his homepage):
-
Thursday, December 6, 2001, 4:15pm in Gates room B01
A Computer Musing lecture entitled
``Totally Acyclic Digraphs (Spiders) and how to squish them''.
-
Tuesday 3 September 2002, 2:15pm in the Lille Auditorium at IFI
(Institutt for informatikk, University of Oslo)
a lecture entitled ``Deconstructing Coroutines''.
-
Tuesday 10 September 2002, Oxford University Com Lab, 4:30pm
a lecture entitled ``Deconstructing Coroutines''.
-
Papers that refer to this one:
-
Richard S. Bird,
Spider spinning for dummies,
Advanced Functional Programming,
Lecture Notes in Computer Science (LNCS), 2009, Volume 5832/2009,
39-65, DOI: 10.1007/978-3-642-04652-0_2
-
Emilio Di Giacomoa, Giuseppe Liottaa, Henk Meijerb, and Stephen K. Wismath,
Volume requirements of 3D upward drawings,
Discrete Mathematics, Volume 309, Issue 7, 8 April 2009, Pages 1824-1837.
Back to list of publications.
