如何对一个由相互链接的元组组成的列表进行排序？

Question

lst = [(u'course', u'session'), (u'instructor', u'session'), (u'session', u'trainee'), (u'person', u'trainee'), (u'person', u'instructor'), (u'course', u'instructor')]

我有一个元组列表，需要按照以下逻辑排序... 每个元组的第二个元素依赖于第一个元素，例如(course, session) -> session依赖于course等等。

我想要一个根据它们的依赖优先级排序的排序列表，更少或独立的对象将首先出现，因此输出应该如下:

lst = [course, person, instructor, session, trainee]

- Avadhesh

Answer 1

你正在寻找所谓的拓扑排序。维基百科页面展示了经典的 Kahn 和深度优先搜索算法；Python 示例在这里（有点过时，但仍可运行），位于pypi（稳定且可重用——你也可以在这里在线阅读代码）和这里（Tarjan 算法，也能处理指定的依赖关系中的循环），只是其中的几个示例。

- Alex Martelli

Answer 2

概念上，您需要创建一个有向无环图，其边由列表内容确定，然后在图上执行拓扑排序。Python标准库中不存在执行此操作的算法（至少我头脑中没有想到），但是您可以在网上找到许多第三方实现，例如http://www.bitformation.com/art/python_toposort.html。

该网站上的函数接收所有字符串的列表items和字符串对之间的另一个列表partial_order。应将lst作为第二个参数传递。要生成第一个参数，可以使用itertools.chain.from_iterable(lst)，因此整个函数调用将是：

import itertools
lst = ...
ordering = topological_sort(itertools.chain.from_iterable(lst), lst)

或者您可以修改网站上的函数，仅接受一个参数，并直接从您的lst中的值创建图中的节点。

编辑：使用Alex Martelli链接到的topsort模块，您可以直接传递lst。

- David Z