Как отсортировать список взаимосвязанных кортежей?

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

У меня над списком кортежей, мне нужно отсортировать его со следующей логикой .... каждый второй элемент tuple зависит от 1-го элемента, например. (Конечно, сессия) -> сессия зависит от курса и так далее ..

Я хочу отсортированный список, основанный на приоритете их зависимости, менее или независимый объект выйдет первый так, что вывод должен быть, как показано ниже,

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

Answer 1

Вы ищете то, что называется topological sort. На странице wikipedia показаны классические алгоритмы Kahn и глубины поиска; Примеры Python: here (немного устарел, но все равно должен работать нормально), на pypi (стабильный и многоразовый - вы также можете прочитать код онлайн here) и here (алгоритм Тарьяна, который также имеет дело с циклами в зависимостях), просто чтобы назвать несколько.

Answer 2

Концептуально, что вам нужно сделать, это создать 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.

EDIT: Использование модуля topsort Алекс Мартелли, связанный с, вы могли бы просто передать lst непосредственно.