A GRAY CODE FOR THE IDEALS OF A FOREST POSET

We present two algorithms for listing all the 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 it 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. © 1993 Academic Press, Inc.