Сортировка списка с неполной функцией сравнения - PullRequest
2 голосов
/ 19 декабря 2009

У меня есть набор объектов, и мне нужно создать отсортированный список, но моя функция сравнения неполная и оставляет некоторое пространство для «воображения» со стороны алгоритма сортировки.

В частности, с учетом коллекции деревьев, подобной следующей:

  A      E
  |      |
  B--C   F
  |
  D

Имеется под рукой набор узлов {A, B, C, D, E, F} в произвольном порядке и функция для проверки прямых отношений родитель-потомок:

parent(A, B)
parent(A, C)
parent(B, D)
parent(E, F)

Мне нужно свести это в список, куда родители приходят раньше, чем их дети, но, кроме этого, порядок не важен. Поэтому любой из этих результатов будет приемлемым:

A, B, C, D, E, F.

A, B, D, C, E, F.

E, F, A, B, C, D.

A, E, B, C, F, D.

Набор будет небольшим, максимум несколько десятков, так что я не слишком беспокоюсь о производительности. Что меня беспокоит, так это избегание временных структур данных, отличных от списков: из-за ограничений языка, который я использую, организация этих элементов во временное дерево (например) была бы неприятной.

Ответы [ 2 ]

4 голосов
/ 19 декабря 2009

Вы можете использовать этот простой алгоритм:

while unsorted set is not empty {
    elem = get element from unsorted set
    while elem has parent and parent is in unsorted set {
        elem = parent of elem
    }
    add elem to result list
    remove elem from unsorted set
}
4 голосов
/ 19 декабря 2009

Я полагаю, вы ищете топологический алгоритм сортировки .

Вот соответствующий алгоритм из статьи в Википедии:

L ← Empty list that will contain the sorted nodes
S ← Set of all nodes

function visit(node n)
    if n has not been visited yet then
        mark n as visited
        for each node m with an edge from n to m do
            visit(m)
        add n to L

for each node n in S do
    visit(n)
Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...