时间戳

首页 > 解决方案 > 如何在没有用元素定义 cmp 运算符的 Python3 中对列表进行排序？

python - 如何在没有用元素定义 cmp 运算符的 Python3 中对列表进行排序？

问题描述

如何在没有用元素定义 cmp 运算符的 Python3 中对列表进行排序？

我想对一个列表进行排序，其中的元素可以通过特定规则相互比较，但没有为它们定义明确的简单比较运算符（例如，<和）。>以这个字典集及其集合（列表）为例：

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()，但达到目的的任何东西都可以！--）

注意：在这个简单的规则中，一个字典可能有多个子字典。在这种情况下，假设这些子哈希之间的关系是未定义的（或者您可以引入另一个规则，例如名称的字母顺序）。无论哪种方式。

[编辑]：
正如评论和答案中所指出的，这是拓扑排序的问题，无法使用内置sort()或sorted()Python (3.8) 实现。现在，澄清一下，我的问题只是“如何实现示例中描述的排序”？
我注意到pip -installable 基本 Python 模块toposort可供它使用（在即将推出的 Python-3.9 中内置实现为functools.TopologicalSorter()。它似乎很有用，尽管这个问题中的情况需要一些工作将其应用于。

标签： pythonpython-3.xalgorithmsortingtopological-sort

解决方案

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

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

也就是说，排序算法需要一组完全有序的条目。那cmp(dBob, dAnn)应该返回 -1，因为 Bob 是 Ann 的孙子。不确定您是否可以从问题中提到的内容中得到。

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

推荐阅读