Ordering Products

[Kay Schluehr]

Here might be an interesting puzzle for people who like sorting
algorithms ( and no I'm not a student anymore and the problem is not a
students 'homework' but a particular question associated with a
computer algebra system in Python I'm currently developing in my
sparetime ).

For motivation lets define some expression class first:

class Expr:
def __init__(self, name=""):
self.name = name
self.factors = [self]

def __mul__(self, other):
p = Expr()
if isinstance(othe r,Expr):
other_factors = other.factors
else:
other_factors = [other]
p.factors = self.factors+ot her_factors
return p

def __rmul__(self, other):
p = M()
p.factors = [other]+self.factors
return p

def __repr__(self):
if self.name:
return self.name
else:
return "*".join([str(x) for x in self.factors])

One can create arbitrary products of Expr objects ( and mixing numbers
into the products ):

a,b,c = Expr("a"),Expr( "b"),Expr(" c")
a*b a*b 7*a*8*9 7*a*8*9

The goal is to evaluate such products and/or to simplify them.

For expressions like
x = 7*a*8*9
this might be easy, because we just have to sort the factor list and
multiply the numbers.
x.factors.sort( )
x a*7*8*9

-> a*504

This can be extended to arbitrary products:
x = 7*a*b*a*9
x.factors.sort( )
x

a*a*b*7*9

-> (a**2)*b*63

Now lets drop the assumption that a and b commute. More general: let be
M a set of expressions and X a subset of M where each element of X
commutes with each element of M: how can a product with factors in M be
evaluated/simplified under the condition of additional information X?

It would be interesting to examine some sorting algorithms on factor
lists with constrained item transpositions. Any suggestions?

Regards,
Kay

[Ron Adam]

Kay Schluehr wrote:

Here might be an interesting puzzle for people who like sorting
algorithms ( and no I'm not a student anymore and the problem is not a
students 'homework' but a particular question associated with a
computer algebra system in Python I'm currently developing in my
sparetime ).

<folded>

x = 7*a*b*a*9
x.factors.s ort()
x

a*a*b*7*9

-> (a**2)*b*63

Now lets drop the assumption that a and b commute. More general: let be
M a set of expressions and X a subset of M where each element of X
commutes with each element of M: how can a product with factors in M be
evaluated/simplified under the condition of additional information X?

It would be interesting to examine some sorting algorithms on factor
lists with constrained item transpositions. Any suggestions?

Regards,
Kay

Looks interesting Kay.

I think while the built in sort works as a convenience, you will need to
write your own more specialized methods, both an ordering (parser-sort),
and simplify method, and call them alternately until no further changes
are made. (You might be able to combine them in the sort process as an
optimization.)

A constrained sort would be a combination of splitting (parsing) the
list into sortable sub lists and sorting each sub list, possibly in a
different manner, then reassembling it back. And doing that possibly
recursively till no further improvements are made or can be made.
On a more general note, I think a constrained sort algorithm is a good
idea and may have more general uses as well.

Something I was thinking of is a sort where instead of giving a
function, you give it a sort key list. Then you can possibly sort
anything in any arbitrary order depending on the key list.

sort(alist, [0,1,2,3,4,5,6,7 ,8,9]) # Sort numbers forward
sort(alist, [9,8,7,6,5,4,3,2 ,1,0]) # Reverse sort
sort(alist, [1,3,5,7,9,0,2,4 ,6,8]) # Odd-Even sort
sort(alist, [int,str,float]) # sort types

These are just suggestions, I haven't worked out the details. It could
probably be done currently with pythons built in sort by writing a
custom compare function that takes a key list. How fine grained the key
list is is also something that would need to be worked out. Could it
handle words and whole numbers instead of letters and digits? How does
one specify which? What about complex objects?
Here's a "quick sort" function that you might be able to play with..
There are shorter versions of this, but this has a few optimizations added.

Overall it's about 10 times slower than pythons built in sort for large
lists, but that's better than expected considering it's written in
python and not C.

Cheers,
Ron

# Quick Sort
def qsort(x):
if len(x)<2:
return x # Nothing to sort.

# Is it already sorted?
j = min = max = x[0]
for i in x:
# Get min and max while checking it.
if i<min: min=i
if i>max: max=i
if i<j: # It's not sorted,
break # so stop checking and sort.
j=i
else:
return x # It's already sorted.

lt = []
eq = []
gt = []

# Guess the middle value based on min and max.
mid = (min+max)//2

# Divide into three lists.
for i in x:
if i<mid:
lt.append(i)
continue
if i>mid:
gt.append(i)
continue
eq.append(i)

# Recursively divide the lists then reassemble it
# in order as the values are returned.
return q(lt)+eq+q(gt)

[Diez B.Roggisch]

Kay Schluehr <kay.schluehr <at> gmx.net> writes:

Now lets drop the assumption that a and b commute. More general: let be
M a set of expressions and X a subset of M where each element of X
commutes with each element of M: how can a product with factors in M be
evaluated/simplified under the condition of additional information X?

It would be interesting to examine some sorting algorithms on factor
lists with constrained item transpositions. Any suggestions?

I don't think that sorting is the answer here.
Firts of all IMHO you have to add an
additional constraint - associativity of the operation in question
So the problem could be reduced to making the constant
parts be more associative than the non-constant parts.
which you should be able to
do with a parser. The BNF grammar could look like this:

expr ::= v_expr "*" v_expr | v_expr
v_expr ::= variable | c_expr
c_expr ::= l_expr "*" literal | l_expr
l_expr ::= literal | "(" expr ")"

The trick is to create a stronger-binding multiplication operator on constants
than on mixed
expressions.

This grammar is ambigue of course - so a LL(k) or maybe even LALR won't work.
But earley's method
implemented in spark should do the trick.
If I find the time, I'll write an short implementation
tomorrow.

Diez

[Kay Schluehr]

Diez B.Roggisch wrote:

Kay Schluehr <kay.schluehr <at> gmx.net> writes:

Now lets drop the assumption that a and b commute. More general: let be
M a set of expressions and X a subset of M where each element of X
commutes with each element of M: how can a product with factors in M be
evaluated/simplified under the condition of additional information X?

It would be interesting to examine some sorting algorithms on factor
lists with constrained item transpositions. Any suggestions?

I don't think that sorting is the answer here.
Firts of all IMHO you have to add an
additional constraint - associativity of the operation in question
So the problem could be reduced to making the constant
parts be more associative than the non-constant parts.
which you should be able to
do with a parser.

Hi Diez,

I have to admit that I don't understand what you mean with the
'constant parts' of an expression?

The associativity of __mul__ is trivially fullfilled for the dummy
class M if an additional __eq__ method is defined by comparing factor
lists because those lists are always flat:

def __eq__(self, other):
if isinstance(othe r,M):
return self.factors == other.factors
return False

The sorting ( or better 'grouping' which can be represented by sorting
in a special way ) of factors in question is really a matter of
(non-)commutativity. For more advanced expressions also group
properties are important:

If a,b are in a center of a group G ( i.e. they commute with any
element of G ) and G supplies an __add__ ( besides a __mul__ and is
therefore a ring ) also a+b is in the center of G and (a+b)*c = c*(a+b)
holds for any c in G.

It would be nice ( and much more efficient ) not to force expansion of
the product assuming distributivity of __add__ and __mul__ and
factorization after the transposition of the single factors but
recognizing immediately that a+b is in the center of G because the
center is a subgroup of G.
Regards,
Kay

[Kay Schluehr]

Ron Adam wrote:

Kay Schluehr wrote:

Here might be an interesting puzzle for people who like sorting
algorithms ( and no I'm not a student anymore and the problem is not a
students 'homework' but a particular question associated with a
computer algebra system in Python I'm currently developing in my
sparetime ).
<folded>

>x = 7*a*b*a*9
>x.factors.s ort()
>x

a*a*b*7*9

-> (a**2)*b*63

Now lets drop the assumption that a and b commute. More general: let be
M a set of expressions and X a subset of M where each element of X
commutes with each element of M: how can a product with factors in M be
evaluated/simplified under the condition of additional information X?

It would be interesting to examine some sorting algorithms on factor
lists with constrained item transpositions. Any suggestions?

Regards,
Kay

Looks interesting Kay.

I think so too :) And grouping by sorting may be interesting also for
people who are not dealing with algebraic structures.
I think while the built in sort works as a convenience, you will need to
write your own more specialized methods, both an ordering (parser-sort),
and simplify method, and call them alternately until no further changes
are made. (You might be able to combine them in the sort process as an
optimization.)

A constrained sort would be a combination of splitting (parsing) the
list into sortable sub lists and sorting each sub list, possibly in a
different manner, then reassembling it back. And doing that possibly
recursively till no further improvements are made or can be made.
I think a comparison function which is passed into Pythons builtin
sort() should be sufficient to solve the problem. I guess the
comparison defines a total order on the set of elements defined by the
list to sort.
On a more general note, I think a constrained sort algorithm is a good
idea and may have more general uses as well.

Something I was thinking of is a sort where instead of giving a
function, you give it a sort key list. Then you can possibly sort
anything in any arbitrary order depending on the key list.

sort(alist, [0,1,2,3,4,5,6,7 ,8,9]) # Sort numbers forward
sort(alist, [9,8,7,6,5,4,3,2 ,1,0]) # Reverse sort
sort(alist, [1,3,5,7,9,0,2,4 ,6,8]) # Odd-Even sort
sort(alist, [int,str,float]) # sort types
Seems like you want to establish a total order of elements statically.
Don't believe that this is necessary.
These are just suggestions, I haven't worked out the details. It could
probably be done currently with pythons built in sort by writing a
custom compare function that takes a key list.
Exactly.
How fine grained the key
list is is also something that would need to be worked out. Could it
handle words and whole numbers instead of letters and digits? How does
one specify which? What about complex objects?

In order to handle complex objects one needs more algebra ;)

Since the class M only provides one operation I made the problem as
simple as possible ( complex expressions do not exist in M because
__mul__ is associative - this is already a reduction rule ).

Kay

[Bernhard Holzmayer]

Kay Schluehr wrote:

Now lets drop the assumption that a and b commute. More general: let be
M a set of expressions and X a subset of M where each element of X
commutes with each element of M: how can a product with factors in M be
evaluated/simplified under the condition of additional information X?

It would be interesting to examine some sorting algorithms on factor
lists with constrained item transpositions. Any suggestions?

Hello Kay,

take this into account:
Restrictions like commutativity, associative, distributive and flexibility
laws don't belong neither to operands nor to operators themselves.
Instead these are properties of fields (set of numbers with respect to a
certain operation).
For a famous example for a somewhat "alternativ e" behaviour look at the
Octonions (discovered in 1843 by Graves and 1845 by Cayley), which are not
associative with respect to addition and/or multiplication.
(http://en.wikipedia.org/wiki/Octonions) or the Quarternions, which are
non-commutative (http://en.wikipedia.org/wiki/Quaternion)

Obviously, it's not correct to say: addition is associative, or, that
multiplication is. With the same right, you could say, multiplication is
not associative.
With the same reasoning, we can show that it's not easy to generalize
sorting, commutation, association or distribution mechanisms.

Maybe it would be a very fascinating goal to solve your algorithmic approach
in such a limited environment like the Quarternions.
A solution for this set of numbers, if achieved in a clean, mathematically
abstract way, should hold for most other numbers/fields too, natural and
real included.

I guess that the approach might be this way:
- define/describe the fields which shall be handled
- define/describe the rules which shall be supported
- find methods to reduce sequences of operations to simple binary or unary
operations (tokens) - this may introduce brackets and stacking mechanisms
- a weighing algorithm might be necessary to distinguish between plain
numbers and place holders (variables)
- application of the distributivity (as far as possible) might help to find
a rather flat representation and a base for reordering according to the
weights of the individual sub-expressions

Nevertheless, there are lots of commercial programs which do such sort of
symbolic mathematics, and which would badly fail when it would come to such
awkward fields like Quarternions/Octonions.
Bernhard

[Diez B.Roggisch]

> I have to admit that I don't understand what you mean with the

'constant parts' of an expression? From what I percieved of your example it seemed to me that you wanted to evaluate the constants like 7*9 first, so that an expression like

a * 7 * 9 * b

with variables a,b is evaluated like this:

a * 63 * b

So my suggestion was simply to make the *-operator more precedent when
in between two constants. What I mean with constants here are of course
integer/float literals. The concept of a differing operator precedence
can be extended to arbitray elements when their types are known - which
should be possible when variable values are known at parsing
time.
The associativity of __mul__ is trivially fullfilled for the dummy
class M if an additional __eq__ method is defined by comparing factor
lists because those lists are always flat:
I don't care about that, as my approach deosn't use python's built-in parser
- it can't, as that wouldn't allow to re-define operator precedence.

What you do is to
simply collect the factors as list. But what you need (IMHO) is a parsing
tree (AST) that reflects your desired behaviour by introducing a different
precedence thus that the expression

a * 7 *9 * b

is not evaluated like

((a*7)*9)*b

(which is a tree, and the standard way of evaluationg due to built-in parsers
precedence rules) but as

a*(7*9)*b

which is also a tree.
The sorting ( or better 'grouping' which can be represented by sorting
in a special way ) of factors in question is really a matter of
(non-)commutativity. For more advanced expressions also group
properties are important:
No, IMHO associativity is the important thing here - if

(a * 7) * 9

yields a different solution than

a *(7*9)

your reordering can't be done - in the same way as re-arranging
factors a*b to b*a only works if the commute - or, to put in in
algebraic terms, the group is abelian.
If a,b are in a center of a group G ( i.e. they commute with any
element of G ) and G supplies an __add__ ( besides a __mul__ and is
therefore a ring ) also a+b is in the center of G and (a+b)*c = c*(a+b)
holds for any c in G.

It would be nice ( and much more efficient ) not to force expansion of
the product assuming distributivity of __add__ and __mul__ and
factorization after the transposition of the single factors but
recognizing immediately that a+b is in the center of G because the
center is a subgroup of G.

Well, you don't need to expand that product - the subexpression a+b is
evaluated first. If you can sort of "cache" that evaluation's result because
the expressions involved are of a constant nature, you can do so.

The rason (a+b) is evaluated first (at least in the standard python parser,
and in my proposed special parser) is that the parentheses ensure that.

To sum things up a little: I propose not using the python built-in parser
which results in you having to overload operators and lose control
of precedence, but by introducing your own parser, that can do the
trick of re-arranging the operators based on not only the "usual" precedence
(* binds stronger than +), but by a type-based parser that can even change
precedence of the same operator between different argument types is's
applied to. That might sound complicated, but I think the grammar
I gave in my last post shows the concept pretty well.

regards,

Diez

[Ron Adam]

Kay Schluehr wrote:

Ron Adam wrote:

Kay Schluehr wrote: On a more general note, I think a constrained sort algorithm is a good
idea and may have more general uses as well.

Something I was thinking of is a sort where instead of giving a
function, you give it a sort key list. Then you can possibly sort
anything in any arbitrary order depending on the key list.

sort(alist, [0,1,2,3,4,5,6,7 ,8,9]) # Sort numbers forward
sort(alist, [9,8,7,6,5,4,3,2 ,1,0]) # Reverse sort
sort(alist, [1,3,5,7,9,0,2,4 ,6,8]) # Odd-Even sort
sort(alist, [int,str,float]) # sort types

Seems like you want to establish a total order of elements statically.
Don't believe that this is necessary.

I want to establish the sort order at the beginning of the sort process
instead of using many external compares during the sort process. Using
a preprocessed sort key seems like the best way to do that. How it's
generated doesn't really matter. And of course a set of standard
defaults could be built in.

These are just suggestions, I haven't worked out the details. It could
probably be done currently with pythons built in sort by writing a
custom compare function that takes a key list.

Exactly.

The advantage of doing it as above would be the sort could be done
entirely in C and not need to call a python compare function on each
item. It would be interesting to see if and how much faster it would
be. I'm just not sure how to do it yet as it's a little more
complicated than using integer values.

How fine grained the key
list is is also something that would need to be worked out. Could it
handle words and whole numbers instead of letters and digits? How does
one specify which? What about complex objects?

In order to handle complex objects one needs more algebra ;)

Since the class M only provides one operation I made the problem as
simple as possible ( complex expressions do not exist in M because
__mul__ is associative - this is already a reduction rule ).

Kay

I'm played around with your example a little bit and think I see how it
should work... (partly guessing) You did some last minute editing so M
and Expr were intermixed.

It looks to me that what you need to do is have the expressions stored
as nested lists and those can be self sorting. That can be done when
init is called I think, and after any operation.

You should be able to add addition without too much trouble too.

a*b -> factors [a],[b] -> [a,b] You got this part.

c+d -> sums [c],[d] -> [c,d] Need a sums type for this.

Then...

a*b+c*d -> sums of factors -> [[a,b],[c,d]]

This would be sorted from inner to outer.

(a+b)*(b+c) -> factors of sums -> [[a,b],[c,d]]

Maybe you can sub class list to create the different types? Each list
needs to be associated to an operation.

The sort from inner to outer still works. Even though the lists
represent different operations.

You can sort division and minus if you turn them into sums and factors
first.

1-2 -> sums [1,-2]

3/4 -> factors [3,1/4] ? hmmm... I don't like that.

Or that might be...

3/4 -> factor [3], divisor [4] -> [3,[4]]
So you need a divisor type as a subtype of factor. (I think)
You can then combine the divisors within factors and sort from inner to
outer.

(a/b)*(c/e) -> [a,[b],c,[e]] -> [a,c,[b,e]]

Displaying these might take a little more work. The above could get
represented as...

(a*c)/(b*e)

Which I think is what you want it to do.
Just a few thoughts. ;-)
Cheers,
Ron

[Kay Schluehr]

Bernhard Holzmayer schrieb:

Kay Schluehr wrote:

Now lets drop the assumption that a and b commute. More general: let be
M a set of expressions and X a subset of M where each element of X
commutes with each element of M: how can a product with factors in M be
evaluated/simplified under the condition of additional information X?

It would be interesting to examine some sorting algorithms on factor
lists with constrained item transpositions. Any suggestions?

Hello Kay,

take this into account:
Restrictions like commutativity, associative, distributive and flexibility
laws don't belong neither to operands nor to operators themselves.
Instead these are properties of fields (set of numbers with respect to a
certain operation).
For a famous example for a somewhat "alternativ e" behaviour look at the
Octonions (discovered in 1843 by Graves and 1845 by Cayley), which are not
associative with respect to addition and/or multiplication.
(http://en.wikipedia.org/wiki/Octonions) or the Quarternions, which are
non-commutative (http://en.wikipedia.org/wiki/Quaternion)

Obviously, it's not correct to say: addition is associative, or, that
multiplication is. With the same right, you could say, multiplication is
not associative.

It was associative in the tiny example I presented. I did not mentioned
to discuss the evolving structure of the whole CAS here in detail which
would be better done in an own newsgroup once an early version is
released.

Maybe the setting of the original question should be made more precise:
associative, non-commutative multiplicative groups.

Handling non-associative algebras like Lie algebras is a completely
different matter and I'm not even sure which one is the best way to
represent operations in Python?

Maye this way?

lie = Lie() # create an arbitrary Lie algebra (lie is again a class )
A,B = lie(),lie() # create two arbitrary elements of the Lie algebra
lie[A,B] # create the commutator of the lie algebra by overloading lie[A,B] # the __getitem__ method
lie[A,B] == -lie[-A,B] True

If one wants to enforce assertions like
lie[r*A,B] == r*lie[A,B] True

for certain elements r of some group acting on lie, one must refine
creation of lie in the initial assignment statement e.g.
lie = Lie(V)

where V is some vectorspace and the elements of lie are homomorphisms
on V. V is created elsewhere. There are a lot of constraints induced by
all the objects dynamically coupled together.
With the same reasoning, we can show that it's not easy to generalize
sorting, commutation, association or distribution mechanisms.

Maybe it would be a very fascinating goal to solve your algorithmic approach
in such a limited environment like the Quarternions.
No CAS can represent infinitely many different representations of
quaternions. But it should not be to hard to deal with an algebra that
represents admissable operations on quaternions in an abstract fashion.
A solution for this set of numbers, if achieved in a clean, mathematically
abstract way, should hold for most other numbers/fields too, natural and
real included.

I guess that the approach might be this way:
- define/describe the fields which shall be handled
- define/describe the rules which shall be supported
- find methods to reduce sequences of operations to simple binary or unary
operations (tokens) - this may introduce brackets and stacking mechanisms
- a weighing algorithm might be necessary to distinguish between plain
numbers and place holders (variables)
- application of the distributivity (as far as possible) might help to find
a rather flat representation and a base for reordering according to the
weights of the individual sub-expressions

Nevertheless, there are lots of commercial programs which do such sort of
symbolic mathematics, and which would badly fail when it would come to such
awkward fields like Quarternions/Octonions.

If you take a look on Mathematica or Maple both programs seem to
interpret pure symbols as members of an associative and commutative
algebra:

expand( (a+x)^2) -> a^2 + 2ax + x^2

This works very fast and accurate but is mathematically too restricted
for me. For doing more advanced stuff one needs to do a lot of
programming in either language shipped with the CAS for creating new
packages. But then I ask myself: why not doing the programming labor in
Python and redesign and optimize the core modules of the CAS if
necessary?

Kay

[Bernhard Holzmayer]

I see, you're sensitive for the difficulties which might arise.
That's the thing I wanted to point out.
Maybe I was looking too far forward...

My first thought was to add attributes/qualifiers to the operands to improve
the sorting.
Then I realized that these attributes/qualifiers were related to the
operators, since multiplication and division use the same operands, but
while in one case it is associative and commutative, it isn't in the other.

I agree that all this leads too far.
But one thing creeps into my mind again:

I guess you'll always need an inverse operation:
A class which can handle multiplication will certainly require an inverse
operation like division.

Bernhard