[EMAIL PROTECTED] wrote:
> I am trying to write some code that will take a list of functional
> expressions, and order them so that those with primitive terms appear
> at the beginning of the list and those that are defined by other terms
> appear last.
>
> eg:
> getSortedEquations(['b = w + z','a = z - y','w = 2*z + v','z = e +
> f','y = p + l']) =
> ['w = 2*z + v', 'z = e + f', 'y = p + l', 'b = w + z', 'a = z -
> y']
>
> It is easy enough to tokenise each of the equations and produce a list
> like:
> ['b', ['w','z']], ['a': ['z','y']], ['w':'z','v'] , ['z', ['e','f']],
> ['y',['p','l']]
>
> But I'd like to find an algorithm that can handle the sorting problem.
>
> So I suspect that this is a common problem for those familiar with
> partially ordered sets or directed graphs. I'm wondering if anyone else
> is familiar with this problem and knows an efficient algorithm that
> will solve it. It would be good if any such algorithm would be able to
> check for circular definitions in the input.
>
First, put them in a list:
L = [['b', ['w','z']], ['a', ['z','y']], ['w', 'z','v'], ['z',
['e','f']], ['y', ['p','l']]]
then sort the list:
def Compare(X, Y):
if X[0] in Y[1]:
return -1
elif Y[0] in X[1]:
return 1
else:
return 0
L.sort(cmp = Compare)
The result is:
[['z', ['e', 'f']], ['b', ['w', 'z']], ['y', ['p', 'l']], ['a', ['z',
'y']], ['w', 'z', 'v']]
It's left as an exercise for the reader as to how it works. :-)
--
http://mail.python.org/mailman/listinfo/python-list
