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
For motivation lets define some expression class first:
def __init__(self, name=""):
self.name = name
self.factors = [self]
def __mul__(self, other):
p = Expr()
other_factors = other.factors
other_factors = [other]
p.factors = self.factors+other_factors
def __rmul__(self, other):
p = M()
p.factors = [other]+self.factors
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")
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.
This can be extended to arbitrary products:
>>> x = 7*a*b*a*9
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?