3
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]
4

2 回答 2

5

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

于 2010-06-30T05:42:01.050 回答
4

从概念上讲,您需要做的是创建一个有向无环图,其边由列表的内容确定,然后对图进行拓扑排序。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-30T05:41:58.253 回答