如何对链接元组列表进行排序？

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]

来源

2010-06-30 Avadhesh

你在寻找什么叫做topological sort。维基百科页面显示了经典的Kahn和深度优先搜索算法; Python的例子是here（有点过时，但还是应该运行正常），对pypi（稳定和可重复使用 - 你也可以阅读代码在线here）和here（的Tarjan的算法，那种，也与依赖周期涉及指定），仅举几例。

来源

2010-06-30 05:42:01

从概念上讲，您需要做的是创建一个由您的列表内容决定的边的directed acyclic graph，然后在图上执行topological sort。在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中的值。

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

来源

2010-06-30 05:41:58

如何对链接元组列表进行排序？

回答

相关问题