Come ordinare un elenco di tuple interconnesse?

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

Non ho che questo elenco di tuple, ho bisogno di ordinare con seguente logica .... 2 ° elemento di ogni tupla dipende dal primo elemento, per esempio (Naturalmente, session) -> sessione dipende da golf e così via ..

Voglio un elenco ordinato in base alla priorità della loro dipendenza, o meno oggetto indipendente arriverà prima in modo di uscita dovrebbe essere come qui di seguito,

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

Answer 1

siete alla ricerca di quello che è chiamato un topologica sorta . Pagina di Wikipedia spettacoli classici algoritmi Kahn e in profondità-ricerca per esso; Esempi di Python sono qui (un po 'datato, ma dovrebbe comunque funzionare bene), su PyPI (stabile e riutilizzabile - si può anche leggere il codice in linea qui ) e qui (algoritmo di Tarjan, quel genere di-anche accordi con cicli nelle dipendenze specificate), solo per citarne alcuni.

Answer 2

Concettualmente, ciò che devi fare è creare un diretto aciclico grafico con bordi determinati dalla il contenuto della lista, e poi fare un topologica sorta sul grafico. L'algoritmo per fare questo non esiste nella libreria standard di Python (almeno, non che mi viene in mente la parte superiore della mia testa), ma è possibile trovare un sacco di implementazioni di terze parti in linea, come ad esempio http://www.bitformation.com/art/python_toposort.html

La funzione in quel sito web richiede un elenco di tutte le stringhe, items, e un altro elenco delle coppie tra stringhe, partial_order. Il tuo lst dovrebbe essere passato come secondo argomento. Per generare il primo argomento, è possibile utilizzare itertools.chain.from_iterable(lst), in modo che la chiamata di funzione complessivo sarebbe

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

Oppure si potrebbe modificare la funzione dal sito web di prendere solo un argomento, e per creare i nodi del grafo direttamente dai valori nel vostro lst.

Modifica :. Utilizzando il modulo topsort Alex Martelli legato a, si può solo passare direttamente lst