# Tutorial :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]  ``

### Solution:1

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.

### Solution:2

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.

Note:If u also have question or solution just comment us below or mail us on toontricks1994@gmail.com
Previous
Next Post »