unranking a sequence of all linear extensions of a partially ordered set

Question

• Let $P$ be a partially ordered set.
• Let $E$ be the set of all possible linear extensions of $P$.
• Let $S$ be the sequence formed by arranging elements of $E$ in lexicographic or graycode order.

Does an unranking function exist that maps $n$ to $S_n$?

In other words, does an efficient mapping exist between the set of linear extensions, and the set of corresponding lexicographic/gray codes (the same way it does for regular combinations and permutations)?

Answer 1

Build the Hasse diagram of the lattice of ideals of a given poset. All max length paths from source to sink in the digraph correspond to a linear extension. See section 2.2 and 3.2 of "Efficient computation of rank probabilities in posets" by Karel De Loof and Computing all simple paths in a distributive lattice in parallel..

Once you have the graph, and the count information provided by section 3.2.2 of the above paper, an encoding scheme based on intervals can efficiently unrank the $n$th linear extension. See: https://cs.stackexchange.com/a/16437/10979.