如何对互相关联的元组列表排序？

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')]

我有一个元组的列表，我需要按照以下逻辑对它进行排序……每个元组的第二个元素是依赖于第一个元素的，比如说（课程，学期）——学期是依赖于课程的，依此类推……

我想要一个根据依赖优先级排序的列表，依赖关系少或者独立的对象应该排在前面，所以输出应该像下面这样，

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

Answer 1

简单来说，你需要做的是创建一个叫做有向无环图的东西，这个图的边是根据你列表里的内容来决定的。然后，你需要对这个图进行拓扑排序。不过，Python的标准库里没有这个算法（至少我现在想不起来有），但你可以在网上找到很多第三方的实现，比如这个链接。

那个网站上的函数需要两个参数，第一个是所有字符串的列表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。

Answer 2

你在寻找一种叫做拓扑排序的方法。维基百科上介绍了经典的Kahn算法和深度优先搜索算法；Python的示例可以在这里找到（虽然有点旧，但应该还是能正常运行），在pypi上也有（稳定且可重复使用——你还可以在线查看代码，链接在这里），还有这里的Tarjan算法，它也能处理指定依赖关系中的循环问题，以上只是举几个例子。