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