Ordering Products

[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