Abstract: A Gray Code for the Ideals of a Forest Poset
A Gray Code for the Ideals of a Forest Poset
Yasunori Koda, Department of Computer Science, University of Victoria.
Frank Ruskey, Department of Computer Science, University of Victoria.
Abstract:
We present two algorithms for listing all ideals of a forest poset.
These algorithms generate ideals in a Gray Code manner; that is,
consecutive ideals differ by exactly one element.
Both algorithms use storage O(n), where n is the number
of elements in the poset. On each iteration, the first algorithm does a
partial traversal of the current ideal being listed
and runs in time O(nN), where N is the number of
ideals of the poset. The second algorithm mimics the first,
but eliminates the traversal and runs in time
O(N). This algorithm has the property that
the amount of computation between successive
ideals is O(1); such algorithms are said to be loopless.
Comments:
- The files here contain an appendix with an implementation that was not
included in the journal paper:
ForestIdeals.dvi,
ForestIdeals.ps.
- Appeared in Journal of Algorithms, 15 (1993) 324-340.
- Does anybody know where Y. Koda is now?
- Donald Knuth liked this algorithm so much that he couldn't resist
developing his own implementation.
See his CWEB program
KODA-RUSKEY .
- This Gray code was generalized to the ideals of "acyclic" posets
and presented at the 26th S.E. Conference on Combinatorics, Graph Theory
and Computing in 1995 (see "spider squishing
talk").
Selected papers that refer to this paper:
-
Richard Bird,
Pearls of Functional Algorithm Design,
book, Cambridge University Press, 2010.
-
Johannes Kanig and Jean-Christophe Filliatre,
Who: A Verifier for Effectful Higher-Order Programs,
ACM SIGPLAN Workshop on ML, Edinburgh, Scotland, UK, August 2009.
-
Gabriela Alexe, Sorin Alexe, Tibéus O. Bonates and Alexander Kogana,
Logical analysis of data - the vision of Peter L. Hammer,
Annals of Mathematics and Artificial Intelligence
49 (2007) 265-312,
-
Sorin Alexe and Peter Hammer,
Accelerated Algorithm For Pattern Detection In Logical Analysis
Of Data, Discrete Applied Mathematics, 2006.
-
Karel De Loof, Hans De Meyer, Bernard De Baets,
Exploiting the Lattice of Ideals Representation of a Poset,
Fundamenta Informaticae, 71 (2006) 309-321.
-
Jayme L. Szwarcfiter,
Generating All Forest Extensions of a Partially Ordered Set,
Algorithms and Complexity: 5th Italian Conference, CIAC 2003,
Lecture Notes in Computer Science, 2653 (2003) 132-139.
-
Jean-Christophe FilliÂtre and FranÇois Pottier,
Producing all ideals of a forest, functionally,
Journal of Functional Programming, 13 (2003), 945-956.
-
Svante Janson,
Ideals In A Forest, One-Way Infinite Binary Trees And The
Contraction Method.
In ``Mathematics and Computer Science, II (Versailles, 2002),
Trends in Mathematics, Pages 393-414.
Birkhauser, Basel, 2002.
-
M. Habib, R. Medina, L. Nourine, G. Steiner,
Efficient Algorithms on Distributive Lattices,
Discrete Applied Mathematics, 110 (2001) 169-187.
-
E. Rodney Canfield and S. Gill Williamson,
A loop-free algorithm for generating the
linear extensions of a poset,
Order, 12 (1995) 57-75.
Back
to Frank Ruskey's publication list.