language-agnostic - 排序一个poset？

Question

那里有大量的排序算法，但它们中的大多数只适用于完全有序的集合，因为它们假设任何两个元素都是可比的。但是，有没有什么好的算法可以对一些元素进行排序，其中一些元素是无法比较的？也就是说，给定一组 S 元素从一个偏序中抽取，如果 x _i ≤ x _{j ， i ≤ j，输出一个排序 x 1} , x ₂ , ..., x _n的最佳方法是什么？

Answer 1

arxiv.org上有一篇题为Sorting and Selection in Posets的论文，其中讨论了 O((w^2)nlog(n/w)) 阶的排序方法，其中 w 是poset 的“宽度”。我没有读过这篇论文，但它似乎涵盖了你正在寻找的内容。

Answer 2

拓扑排序非常适合对部分有序集进行排序。大多数算法都是 O(n^2)。这是来自维基百科的算法：

L ← Empty list that will contain the sorted elements
S ← Set of all nodes with no incoming edges
while S is non-empty do
    remove a node n from S
    add n to tail of L
    for each node m with an edge e from n to m do
        remove edge e from the graph
        if m has no other incoming edges then
            insert m into S
if graph has edges then
    return error (graph has at least one cycle)
else 
    return L (a topologically sorted order)

有一个有用的视频示例。大多数类 Unix 系统都有该tsort命令。您可以通过以下方式解决视频的巧克力蛋糕示例tsort：

$ cat brownies.txt
preheat bake
water mix
dry_ingredients mix
grease pour
mix pour
pour bake

$ tsort brownies.txt
grease
dry_ingredients
water
preheat
mix
pour
bake

Answer 3

我将从选择交换排序开始。那是 O(n^2)，我认为你不会做得比这更好。