443,492 Members | 1,242 Online Need help? Post your question and get tips & solutions from a community of 443,492 IT Pros & Developers. It's quick & easy.

# Ordering Products

 P: n/a 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 Jul 21 '05 #1
15 Replies

 P: n/a Kay Schluehr 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 Jul 21 '05 #3

 P: n/a Diez B.Roggisch wrote: Kay Schluehr 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 Jul 21 '05 #4

 P: n/a Kay Schluehr wrote: 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? Hello Kay, take this into account: Restrictions like commutativity, associative, distributive and flexibility laws don't belong neither to operands nor to operators themselves. Instead these are properties of fields (set of numbers with respect to a certain operation). For a famous example for a somewhat "alternative" behaviour look at the Octonions (discovered in 1843 by Graves and 1845 by Cayley), which are not associative with respect to addition and/or multiplication. (http://en.wikipedia.org/wiki/Octonions) or the Quarternions, which are non-commutative (http://en.wikipedia.org/wiki/Quaternion) Obviously, it's not correct to say: addition is associative, or, that multiplication is. With the same right, you could say, multiplication is not associative. With the same reasoning, we can show that it's not easy to generalize sorting, commutation, association or distribution mechanisms. Maybe it would be a very fascinating goal to solve your algorithmic approach in such a limited environment like the Quarternions. A solution for this set of numbers, if achieved in a clean, mathematically abstract way, should hold for most other numbers/fields too, natural and real included. I guess that the approach might be this way: - define/describe the fields which shall be handled - define/describe the rules which shall be supported - find methods to reduce sequences of operations to simple binary or unary operations (tokens) - this may introduce brackets and stacking mechanisms - a weighing algorithm might be necessary to distinguish between plain numbers and place holders (variables) - application of the distributivity (as far as possible) might help to find a rather flat representation and a base for reordering according to the weights of the individual sub-expressions Nevertheless, there are lots of commercial programs which do such sort of symbolic mathematics, and which would badly fail when it would come to such awkward fields like Quarternions/Octonions. Bernhard Jul 21 '05 #6

 P: n/a I see, you're sensitive for the difficulties which might arise. That's the thing I wanted to point out. Maybe I was looking too far forward... My first thought was to add attributes/qualifiers to the operands to improve the sorting. Then I realized that these attributes/qualifiers were related to the operators, since multiplication and division use the same operands, but while in one case it is associative and commutative, it isn't in the other. I agree that all this leads too far. But one thing creeps into my mind again: I guess you'll always need an inverse operation: A class which can handle multiplication will certainly require an inverse operation like division. Bernhard Jul 21 '05 #10

 P: n/a Kay Schluehr wrote: 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: This works for (simple) expressions with mixed multiplication and addition. class F(list): def __init__(self,*x): #print '\nF:',x list.__init__(self,x) def __add__(self, other): return A(self,other) def __radd__(self, other): return A(other,self) def __mul__(self, other): return M(self,other) def __rmul__(self, other): return M(other,self) def __repr__(self): return str(self) def __order__(self): for i in self: if isinstance(i,A) \ or isinstance(i,M): i.__order__() self.sort() class A(F): def __init__(self, *x): #print '\nA:',x list.__init__(self, x) def __repr__(self): self.__order__() return "+".join([str(x) for x in self]) class M(F): def __init__(self,*x): #print '\nM:',x list.__init__(self,x) def __repr__(self): self.__order__() return "*".join([str(x) for x in self]) a = F('a') b = F('b') c = F('c') d = F('d') print '\n a =', a print '\n b+a+2 =', b+a+2 print '\n c*b+d*a+2 =', c*b+d*a+2 print '\n 7*a*8*9+b =', 7*a*8*9+b a = a b+a+2 = 2+a+b c*b+d*a+2 = 2+a*d+b*c 7*a*8*9+b = 9*8*7*a+b <-- reverse sorted digits? The digits sort in reverse for some strange reason I haven't figured out yet, but they are grouped together. And expressions of the type a*(c+b) don't work in this example. It probably needs some better logic to merge adjacent like groups. I think the reverse sorting my be a side effect of the nesting that takes place when the expressions are built. Having the digits first might be an advantage as you can use a for loop to add or multiply them until you get to a not digit. Anyway, interesting stuff. ;-) Cheers, Ron Jul 21 '05 #11

 P: n/a Diez B.Roggisch wrote: I have to admit that I don't understand what you mean with the 'constant parts' of an expression?From what I percieved of your example it seemed to me that you wanted to evaluate the constants like 7*9 first, so that an expression like a * 7 * 9 * b with variables a,b is evaluated like this: a * 63 * b So my suggestion was simply to make the *-operator more precedent when in between two constants. What I mean with constants here are of course integer/float literals. The concept of a differing operator precedence can be extended to arbitray elements when their types are known - which should be possible when variable values are known at parsing time. O.K. 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: I don't care about that, as my approach deosn't use python's built-in parser - it can't, as that wouldn't allow to re-define operator precedence. Diez, I try not to care too much about global operator precedence of builtin infix operators. The hard problems in designing a CAS beyond Mathematica are related to a bunch of interoperating algebras all defining their own operations. Finally only local precedences exist that are characteristic for certain patterns of expressions with a lot of tangled operators ( e.g. 'geometric algebra' with vector products, wedge products, inner products, additions and subtractions ). I don't want a system defining a syntactically extendable language with 10 custom punctuations per module that no one ( at least not me ) can remind and which looks as awkward as regular expressions. What you do is to simply collect the factors as list. But what you need (IMHO) is a parsing tree (AST) that reflects your desired behaviour by introducing a different precedence thus that the expression a * 7 *9 * b is not evaluated like ((a*7)*9)*b (which is a tree, and the standard way of evaluationg due to built-in parsers precedence rules) but as a*(7*9)*b which is also a tree. Yes, but I tend to use __mul__ just for convenience. It is reflecting an associative and non-commutative operator whereas __add__ is a convenient way to fix an associative and commutative operator. In an idealized mathematical interpretation they represent nothing specific but as language elements they shall be fixed somehow. For more general operations one may define functional operators e.g. r_assoc and l_assoc where following (in)equations hold: l_assoc(a,b,c) == l_assoc(l_assoc(a,b),c) l_assoc(a,b,c) != l_assoc(a, l_assoc(b,c)) r_assoc(a,b,c) == r_assoc(a,r_assoc(b,c)) r_assoc(a,b,c) != r_assoc(r_assoc(a,b),c) This kind of pattern can be used to define rules about l_assoc and r_assoc. Nevertheless, there is no loss of generality. The system lacks prevention from deriving some class providing __mul__ and overwrite the implementation of __mul__ using l_assoc. People may do this on their own risk. Kay Jul 21 '05 #13 