Python: la commande à partir d'une liste de valeurs parents des enfants

Question

J'ai une liste de tuples parents d'enfants

childParentList = [('green', 'blue'), ('red', 'blue'), ('black', 'green'), ('white', 'red')] 

Comment puis-je obtenir l'ordre topologiques de cette liste à partir de critères d'évaluation des enfants.

par exemple: le résultat que vous retourneriez

['black', 'white'] 
['green', 'red'] 
['blue'] 

un autre exemple:

childParentList = [('car', 'table'), ('wheel', 'chair'), ('floor', 'chair'), ('chair', 'light'), ('chair', 'dark'), ('light', 'car'), ('dark', 'car')] 

génèrerait

['wheel', 'floor'] 
['chair'] 
['dark', 'light'] 
['car'] 
['table'] 

Answer 1

En supposant que vous voulez en effet une sorte topologique, vous pouvez utiliser le module toposort(). Cela nécessite que vos données soient organisées dans un dictionnaire d'ensembles.

import toposort,itertools 
as_dict = {k: set(a[1] for a in v) for k,v 
      in itertools.groupby(sorted(childParentList), key=lambda x: x[0])} 
# {'wheel': {'chair'}, 'chair': {'light', 'dark'}, 'dark': {'car'}, 
# 'car': {'table'}, 'floor': {'chair'}, 'light': {'car'}} 

list(toposort.toposort(as_dict)) 
# [{'table'}, {'car'}, {'light', 'dark'}, {'chair'}, {'wheel', 'floor'}]