在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)

（EDIT--这里dBob对dAnn一无所知dAnn对其他人一无所知--）
现在，我想对列表arry进行排序，按照父子关系的顺序排列这些元素

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

实现这一目标的（最佳）方法是什么？
（EDIT——算法不必使用内置的sorted()，但任何达到目的的东西都可以！）

注意：在这个简单规则中，一个字典可能有多个子字典。在这种情况下，比方说，这些子散列之间的关系是未定义的（或者您可以引入另一个规则，例如名称的字母顺序）。不管怎样

[编辑]：
正如在评论和回答中指出的，这是一个topological sorting的问题，不可能用Python（3.8）中的内置sort()或sorted()实现。现在，为了澄清，我的问题只是“如何实现示例中描述的排序”？
我注意到，pip-可安装的基本Python模块toposort可用于它（它是作为functools.TopologicalSorter()在即将发布的Python-3.9中内置实现的）。它似乎很有用，尽管这个问题中的案例需要一些工作来应用它

Answer 1

如果只是比较问题，您可以指定自己的：

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

也就是说，排序算法需要一组完全有序的条目。也就是说cmp(dBob, dAnn)应该返回-1，因为鲍勃是安的孙子。不确定你是否能从你在问题中提到的内容中得到答案

就像@Sneftel提到的，看起来你实际上在寻找的是一种拓扑排序。幸运的是，您可以安装一个toposort包并为其提供算法，但是您需要以正确的格式提供数据（元素字典到它的子元素）

Answer 2

正如所评论的（并反映在编辑的问题中），这种称为topological sorting的排序类型无法通过Python内置的sort实现。相反，它可以使用pip-installable库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的字典进行简单转换。最后，它被转换回一组原始词典的（拓扑排序）列表