algorithm for sorting functional expressions

[chrisguest]

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.

[Marc 'BlackJack' Rintsch]

In <11**********************@16g2000cwy.googlegroups. com>, chrisguest
wrote:

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.

You are looking for "topological sort". Feed a search engine with that
term. :-)

Ciao,
Marc 'BlackJack' Rintsch

[Christian Stapfer]

<ch********@gmail.comwrote in message
news:11**********************@16g2000cwy.googlegro ups.com...

>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.

Right.

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.

Read http://en.wikipedia.org/wiki/Topological_sorting
or just search for "topological sorting" on the net.

Regards,
Christian

[Fredrik Lundh]

Marc 'BlackJack' Rintsch wrote:

>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.

You are looking for "topological sort". Feed a search engine with that
term. :-)

including "python" in the search request might be a good idea. here's a
topsort in Python:

http://mail.python.org/pipermail/pyt...ly/006660.html

(note that most code in that module is for analyzing cycles in case the
sort fails, not for the sort itself).

</F>

[MRAB]

ch********@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. :-)

[Fredrik Lundh]

MRAB wrote:

It's left as an exercise for the reader as to how it works. :-)

*if* it works, you mean. should the following script really print anything?

import random, sys

# input variables replaced with zeros
L = [
['b', ['w','z']],
['a', ['z','y']],
['w', ['z','0']],
['z', ['0','0']],
['y', ['0','0']]
]

def Compare(X, Y):
if X[0] in Y[1]:
return -1
elif Y[0] in X[1]:
return 1
else:
return 0

while 1:
random.shuffle(L)
L.sort(cmp=Compare)
# check that all steps only use known values
i = set("0")
for d, s in L:
if s[0] not in i or s[1] not in i:
print L
print d, s, i
i.add(d)

</F>