Thuật toán để sắp xếp dữ liệu có thể so sánh lỏng lẻo?

Question

Giả sử tôi có một danh sách chưa được phân loại gồm bốn đối tượng: [B, C, A, D]. Tất cả bốn đối tượng là cùng loại, và:
(A> B),
(C> D),

(B = C hoặc D!)
(A = C hoặc D!) (C! = A hoặc B)
(D! = A hoặc B).
Bởi "! =", Tôi có nghĩa là chúng không nhỏ hơn, bằng hoặc lớn hơn các đối tượng khác.

Tôi cần "sắp xếp" danh sách sao cho A sẽ luôn đến trước B và C sẽ luôn đến trước D. Ngoài hai yêu cầu đó, tôi không có yêu cầu về thứ tự của danh sách; do đó, với danh sách được mô tả trước đây, hàm sắp xếp sẽ trả về [A, B, C, D] hoặc [C, D, A, B].

Vì nguyên nhân của vấn đề này, tôi đang cố sắp xếp một mảng các đối tượng java.lang.Class dựa trên mối quan hệ của chúng với nhau. Ví dụ, nếu A là siêu hạng/siêu giao diện của B, thì A nhỏ hơn B. Nếu A mở rộng/triển khai B, thì A lớn hơn B. Nếu A là B, thì rõ ràng A bằng B . Nếu không, A là hoàn toàn không thể so sánh với B.

Cảm ơn trước,
~ Mack

Answer 1

Xây dựng một đồ thị. Đối với mỗi hai yếu tố x và y sao cho x > y, hãy thêm cạnh được hướng từ x đến y. Trong ví dụ của bạn, bạn có A -> B và C -> D. Sau đó chạy topological sort trên biểu đồ này. Phân loại tôpô được trả về sẽ là một giải pháp khả thi.