Sắp xếp một poset?

Question

Có một số lượng lớn các thuật toán sắp xếp trên mạng, nhưng hầu hết chúng chỉ hoạt động trên các tập hợp được sắp xếp hoàn toàn bởi vì chúng giả định rằng bất kỳ hai phần tử nào có thể so sánh được. Tuy nhiên, có bất kỳ thuật toán tốt nào để phân loại các vị trí, trong đó một số phần tử không thể so sánh được? Đó là, cho một tập S các yếu tố rút ra từ một poset, cách tốt nhất để đầu ra là những gì một trật tự x , x , ..., x n ví dụ rằng nếu x _i ≤ x _j, i ≤ j?

Answer 1

Có một giấy có tiêu đề Sorting and Selection in Posets có sẵn trên arxiv.org thảo luận về phương pháp sắp xếp thứ tự O ((w^2) nlog (n/w)), trong đó w là "chiều rộng" của vị trí đặt. Tôi đã không đọc bài báo, nhưng nó có vẻ như nó bao gồm những gì bạn đang tìm kiếm.

Answer 2

Tôi bắt đầu với loại sắp xếp trao đổi. Đó là O (n^2) và tôi không nghĩ rằng bạn sẽ làm tốt hơn thế.

Answer 3

Topological sort rất phù hợp để sắp xếp bộ đặt hàng một phần. Hầu hết các thuật toán là O (n^2). Đây là một thuật toán từ Wikipedia:

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) 

Có một helpful video example. Hầu hết các hệ thống giống Unix đều có lệnh tsort. Bạn có thể giải quyết ví dụ về brownie của video với số tsort như sau:

$ 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