Как отсортировать список в Python3, где с элементами не определен оператор cmp?

Question

Как отсортировать список в Python3, где с элементами не определен оператор cmp?

Я бы хотел отсортировать список, в котором элементы сопоставимы друг с другом с определенным правилом, но там, где для них не определены явные простые операторы сравнения (например, < и >). Возьмем для примера набор словарей и его коллекцию (список):

dNik = { 'id': 'Nik', 'parent': 'Ann' }
dAnn = { 'id': 'Ann', 'parent': ''    }
dBob = { 'id': 'Bob', 'parent': 'Nik' }
arry = [ dNik, dAnn,  dBob ]

Относительное соотношение этих словарей может быть определено; в основном,

Bob (child) < Nik (parent) < Ann (grandparent)

( РЕДАКТИРОВАТЬ - Здесь dBob ничего не знает о dAnn и dAnn ничего не знает о других -)
Итак, я хотел бы отсортировать список arry с перетасованными их элементами в следующем порядке отношения потомок-родитель;

arry = [ dNik, dAnn, dBob ]
sorted(arry, key=lambda i: SOMETHING)
  # => [ dBob, dNik, dAnn ]

Каков (лучший) способ добиться этого?
( РЕДАКТИРОВАТЬ - алгоритм не должен использовать встроенный sorted(), но все, что достигает цели, прекрасно! -)

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

[EDIT] :
Как указано в комментариях и ответе, это проблема топологической сортировки , которую невозможно реализовать с помощью встроенный sort() или sorted() в Python (3.8). Теперь, чтобы уточнить, у меня вопрос просто: «Как выполнить сортировку, как описано в примере»?
Замечу, что pip -установляемый базовый c Python module toposort * Для него доступно 1044 * (которое будет встроено в предстоящем Python -3.9 как functools.TopologicalSorter () . Это кажется полезным, хотя случай в этом вопросе требует немного работы применить его к.

Answer 1

Как прокомментировано (и отражено в отредактированном вопросе), этот тип сортировки, называемый топологическая сортировка , не может быть достигнут с помощью Python встроенного sort. Вместо этого это можно сделать с помощью pip -установляемой библиотеки toposearch , которая будет доступна как встроенная в следующих Python -3.9.

Здесь является ответом на вопрос с использованием библиотеки toposearch:

from toposort import toposort_flatten

lst_sorted = toposort_flatten({i['id']:{i['parent']} for i in arry})
  # => ['', 'Ann', 'Nik', 'Bob']
lst_rev    = list(reversed(lst_sorted[1:]))
  # => ['Bob', 'Nik', 'Ann']
[next(x for x in arry if x['id']==j) for j in lst_rev]
  # => [{'id': 'Bob', 'parent': 'Nik'},
  #     {'id': 'Nik', 'parent': 'Ann'},
  #     {'id': 'Ann', 'parent': ''}]

Описание:
Обе функции в библиотеках toposort должны быть снабжены простым объектом с типом Dict[Any, Set[Any]]. В приведенном выше фрагменте кода выполняется простое преобразование из arry (на вопрос) в словарь типа для передачи в toposort_flatten. Наконец, он преобразуется обратно в (toposorted) список набора исходных словарей.

Answer 2

Если проблема заключается только в сравнении, вы можете указать свою собственную:

sorted(arry, 
       cmp=lambda x, y: x-y # insert custom logic here
      )

При этом алгоритмы сортировки ожидают полностью упорядоченный набор записей. То есть cmp(dBob, dAnn) должно вернуть -1, потому что Боб - внук Энн. Не уверен, что вы можете получить это из того, что вы упомянули в вопросе.

Как упомянуто @Sneftel, похоже, что то, что вы на самом деле ищете, является топологической сортировкой. К счастью, есть пакет toposort, который вы можете установить и предоставит алгоритм для него, но вам нужно будет предоставить ваши данные в правильном формате (словарь элементов для его детей).