如何对相互链接的元组列表进行排序? [英] How to sort a list of inter-linked tuples?

问题描述

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 等等..

I've above list of tuple, I need to sort it with following logic.... each tuple's 2nd element is dependent on 1st element, e.g. (course, session) -> session is dependent on course and so on..

我想要一个基于其依赖优先级的排序列表，较少或独立的对象将首先出现，因此输出应如下所示，

I want a sorted list based on priority of their dependency, less or independent object will come first so output should be like below,

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

推荐答案

您正在寻找所谓的 拓扑排序.维基百科页面展示了经典的 Kahn 和深度优先搜索算法；Python 示例是 here(有点过时，但应该仍然运行良好)，在 pypi(稳定且可重用——你也可以在线阅读代码此处) 和 此处(Tarjan 的算法，这种算法也处理指定依赖项中的循环)，仅举几例.

You're looking for what's called a topological sort. The wikipedia page shows the classic Kahn and depth-first-search algorithms for it; Python examples are here (a bit dated, but should still run fine), on pypi (stable and reusable -- you can also read the code online here) and here (Tarjan's algorithm, that kind-of also deals with cycles in the dependencies specified), just to name a few.

这篇关于如何对相互链接的元组列表进行排序?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！