dependency order

[Diez B. Roggisch]

belred at gmail.com schrieb:
> i'm having trouble trying to figure this out... it's part of a build
> system i'm writing in python.  maybe someone has a good simple way to
> solve this.  i'm trying to create a dependency order out of multiple
> lists.
> 
> list1: B C
> list2: A B
> list3: A C
> 
> i want the end result to be the list: A B C
> i'm very frustrated that i can't come up with anything that always
> works.
> 
> 
> thanks... any clues to solve this would be greatly appreciated.

Maybe the frustration is based on the IMHO wrong data-structure you use. 
What does [B, C] mean?

A common approach for this is to create a dict instead, that maps an 
object to the list of things it depends on (or that depend on it, it's 
essentially the same)

The resulting data-structure is called a directed graph, and there are 
algorithms like "partial orderings" you can google for that will help you.

An example graph would be:


dict(
	"A" : ["B", "C"],
	"B" : ["C"]
  	"C" : []
)

Then the result of a partial ordering would be

["C", "B", "A"]

which should be what you are after.

Diez