How to sort a list of inter-linked tuples?

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

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]

Answer 1

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.

Answer 2

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.