分级偏序(从拓扑排序开始)

Question

这篇博文讨论了拓扑排序的一个有趣的变化:http://jdh.hamkins.org/linear-gradings-of-partial-orders/

偏序的线性分级就像拓扑排序，除了在允许的情况下，顶点可以共享一个"水平"。

如何实现一个程序(比如在Haskell中)来找到偏阶(即DAG)的所有线性分级?

在博客文章的例子中，拓扑排序可以很容易地找到排序[[1]，[2,3,4]，[5]]。然后是Haskell程序

map concat $ sequence $ map concat $ map (map permutations) $ map partitions [[1],[2,3,4],[5]] 

似乎产生了正确的结果。但是，我认为这段代码不能正确地解决一般情况。

Answer 1

根据到目前为止收到的评论，这里是一个答案的草图。

这个代码计算一个列表的有序分区。在适当的偏置数据结构下，avail和update可以用适当的函数代替，我认为逻辑是成立的。

import Control.Monad
import Data.List
delems xs zs = foldr delete zs xs
powerset xs = filterM (x -> [True, False]) xs
-- returns the currently available subsets
avail s = filter (not . null) $ powerset s
-- updates the data structure
update e s = delems e s
ordered_partitions [] = [[]]
ordered_partitions set = do
elems <- avail set
remainder <- ordered_partitions (update elems set)
[elems:remainder]

似乎堆(优先级队列)的poset不是一个广泛实现的事情。这里有一些讨论优先级队列和这里https://cs.stackexchange.com/questions/7890/priority-queue-for-partially-ordered-priorities-with-infima。特别相关的是弱序和偏序之间的区别。弱订单更容易处理。

Kahn的算法似乎很有希望实现这个优先级队列…