On the random generation and counting of weak order extensions of a poset with given class cardinalities

In previous work, we have proposed a simple algorithm to generate random linear extensions of a partially ordered set (poset). A closely related problem is the random generation of so-called weak order extensions of a poset. Such an extension can be informally characterized as a linear order on the equivalence classes of a partition of the poset, not contradicting the underlying poset order. The generation of linear extensions can then be seen as a special case of the generation of weak order extensions where each equivalence class degenerates into a singleton. If no a priori knowledge about the underlying partition is available, time complexity increases tremendously. In first instance, we therefore restrict to the generation of weak order extensions with given class cardinalities, a problem encountered in the context of ranking algorithms. It will be shown that a first random weak order extension can be generated in O(w2(P)·|I(P)|)O(w2(P)·|I(P)|) time, while every subsequent extension with the same class cardinalities can be obtained in O(w(P)·|P|)O(w(P)·|P|) time, where |I(P)||I(P)| denotes the number of ideals of the poset P, and w(P) the width of the poset P  . Additionally, the number of weak order extensions obeying the specified class cardinalities can also be obtained in the stated O(w2(P)·|I(P)|)O(w2(P)·|I(P)|) time.