Tom Jones schrieb: > Hi, > > Consider tuples of the above numbers in the form: > (a,b) > > Suppose this relation means: > a depends on b > > Given a list of tuples, I would like an algorithm to return the proper > ordering of the elements...and if the ordering has a loop (which in this > case, prevents a proper ordering), then it should return None. > > For example, > > > [(1,2),(2,3),(3,4)] > should give: > [4,3,2,1] > > > [(3,2),(1,3),(2,4)] > should give: > [4,2,3,1] > > > [(1,4),(4,3),(2,3)] > should give: > [3,2,4,1] or [3,4,2,1] (which one doesn't matter) > > > [(1,2), (2,3), (3,2)] > should give > None, since it cannot be resolved > > > I'm sure this is a standard problem (mro, resolving inheritance?), but > this is a simplified case since each element can directly depend on only > one other element (thus, multiple inheritance is not allowed)...but many > elements can depend on the same element (no limit on the number of > classes which subclass another class). A quick hack is simple enough to > code, but I am wondering if there are 'standard' ways of performing this > task in this limited scope.
http://en.wikipedia.org/wiki/Topological_sorting Diez -- http://mail.python.org/mailman/listinfo/python-list
