对偏序集进行排序？

Question

有大量的排序算法，但大多数只适用于全序集，因为它们假设任何两个元素都是可比较的。然而，是否有任何好的算法可以对某些元素无法比较的偏序集进行排序？也就是说，给定从偏序集中提取的一组元素 S，输出排序 x₁, x₂, ..., x_n 使得如果 x_i ≤ x_j，i ≤ j？

Answer 1

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

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)，我认为你不会做得更好。