A Gray code for the ideals of a forest poset. (English) Zbl 0782.94014

Summary: We present two algorithms for listing all ideals of a forest poset. These algorithms generate ideals in 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.


94B15 Cyclic codes
06A07 Combinatorics of partially ordered sets
Full Text: DOI Link