Алгоритм сортировки слабо сопоставимых данных?

Question

Допустим, у меня есть несортированный список из четырех объектов: [B, C, A, D].

Все четыре объекта относятся к одному типу и:

  (A > B),
  (C > D),
  (A != C or D)
  (B != C or D)
  (C != A or B)
  (D != A or B).

Под != я имею в виду, что они не меньше, не равны или больше других объектов.

Мне нужно «отсортировать» список так, чтобы A всегда предшествовал B, а C всегда предшествовал D. Помимо этих двух требований, я не требую упорядочения списка; поэтому, учитывая ранее описанный список, функция сортировки должна возвращать либо [A, B, C, D], либо [C, D, A, B].

Что касается причины этой проблемы, я пытаюсь отсортировать массив java.lang.Class объектов на основе их отношений друг с другом. Например, если A является суперклассом / суперинтерфейсом B, то A меньше B. Если A расширяет / реализует B, то A больше B. Если A равно B, то, очевидно, A равно B. В противном случае A совершенно несопоставимо с B.

Answer 1

Построить график. Для каждых двух элементов x и y, таких как x > y, добавьте направленный край от x до y. В вашем примере вы бы получили A -> B и C -> D. Затем выполните топологическую сортировку на этом графике. Возвращенная топологическая сортировка будет возможным решением.