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

发布于 2024-09-07 05:11:02 字数 407 浏览 7 评论 0原文

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]

原文

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

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]

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

魔法少女 2024-09-14 05:11:02

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

回复收藏 0 原文

冰魂雪魄 2024-09-14 05:11:02

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

Conceptually, what you need to do is create a directed acyclic graph with edges determined by the contents of your list, and then do a topological sort on the graph. The algorithm to do this doesn't exist in Python's standard library (at least, not that I can think of off the top of my head), but you can find plenty of third-party implementations online, such as http://www.bitformation.com/art/python_toposort.html

The function at that website takes a list of all the strings, items, and another list of the pairs between strings, partial_order. Your lst should be passed as the second argument. To generate the first argument, you can use itertools.chain.from_iterable(lst), so the overall function call would be

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

Or you could modify the function from the website to only take one argument, and to create the nodes in the graph directly from the values in your lst.

EDIT: Using the topsort module Alex Martelli linked to, you could just pass lst directly.

回复收藏 0 原文

~没有更多了~