Ordering Products

[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(other,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