2

这篇博客文章讨论了拓扑排序的一个有趣变化：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]]

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

4

1 回答 1

0

根据迄今为止收到的评论，这里是一个答案可能是什么样子的草图。

此代码计算列表的有序分区。有了合适的 poset 数据结构，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的堆（优先队列）并不是一个广泛实施的东西。这里有一些讨论Priorities in Priority Queue和这里​​ https://cs.stackexchange.com/questions/7890/priority-queue-for-partially-ordered-priorities-with-infima。特别相关的是弱排序和偏序之间的区别。弱订单更容易处理。

Kahn 的算法似乎很有希望作为实现此优先级队列的一种方式......

于 2021-08-20T09:00:08.177 回答