Home Original page

algorithm for sorting functional expressions

MRAB google at mrabarnett.plus.com
Mon Dec 4 18:18:32 EST 2006 
chrisguest at gmail.com 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. :-)
More information about the Python-list mailing list