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

## Advertising

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(other,Expr):
other_factors = other.factors
else:
other_factors = [other]
p.factors = self.factors+other_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
--
http://mail.python.org/mailman/listinfo/python-list