У меня есть набор объектов, и мне нужно создать отсортированный список, но моя функция сравнения неполная и оставляет некоторое пространство для «воображения» со стороны алгоритма сортировки.
В частности, с учетом коллекции деревьев, подобной следующей:
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.
Набор будет небольшим, максимум несколько десятков, так что я не слишком беспокоюсь о производительности. Что меня беспокоит, так это избегание временных структур данных, отличных от списков: из-за ограничений языка, который я использую, организация этих элементов во временное дерево (например) была бы неприятной.