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

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

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

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

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

Answer 1

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

Answer 2

Концептуально, вам нужно создать направленный ациклический граф с ребрами, определяемыми содержимым вашего списка, а затем выполнить топологическую сортировку на графике.Алгоритм для этого не существует в стандартной библиотеке 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 напрямую.