algorithm for sorting functional expressions

[chrisguest@gmail.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:
getSortedEquati ons(['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]

Re: algorithm for sorting functional expressions

In <1165215032.749 560.171530@16g2 000cwy.googlegr oups.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 "topologica l sort". Feed a search engine with that
term. :-)

Ciao,
Marc 'BlackJack' Rintsch

[Christian Stapfer]

Re: algorithm for sorting functional expressions

<chrisguest@gma il.comwrote in message
news:1165215032 .749560.171530@ 16g2000cwy.goog legroups.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:
getSortedEquati ons(['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 "topologica l sorting" on the net.

Regards,
Christian

[Fredrik Lundh]

Re: algorithm for sorting functional expressions

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 "topologica l 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/python-list/1999-July/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]

Re: algorithm for sorting functional expressions

chrisguest@gmai l.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:
getSortedEquati ons(['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]

Re: algorithm for sorting functional expressions

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=Comp are)
# 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>