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 -- http://mail.python.org/mailman/listinfo/python-list