## 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.

### MSC:

 94B15 Cyclic codes 06A07 Combinatorics of partially ordered sets

### Keywords:

Hamiltonian path; poset; Gray code; ideals; loopless
Full Text: