Ron Adam wrote: > Kay Schluehr wrote: > > > > Hi Ron, > > > > I really don't want to discourage you in doing your own CAS but the > > stuff I'm working on is already a bit more advanced than my > > mono-operational multiplicative algebra ;) > > I figured it was, but you offered a puzzle: > > "Here might be an interesting puzzle for people who like sorting > algorithms ..." > > And asked for suggestions: > > "It would be interesting to examine some sorting algorithms on factor > lists with constrained item transpositions. Any suggestions?" > > So I took you up on it. ;-) > > > BTW.. Usually when people say "I don't want to discourage...", They > really want or mean the exact oppisite.
Yes, but taken some renitence into account they will provoke the opposite. Old game theoretic wisdoms ;) > This is a organizational problem in my opinion, so the challenge is to > organize the expressions in a way that can be easily manipulated > further. Groupings by operation is one way. As far as inheritance > goes, it's just another way to organize things. And different algebra's > and sub-algebra's are just possible properties of a group. The groups > can easily be customized to have their own behaviors or be created to > represent custom unique operations. > > The sort method I'm suggesting here, with examples, is constrained by > the associated properties of the group that is being sorted. Basically, > weather or not it's and associative operation or not. So when a group > is asked to sort, it first asks all it's sub groups to sort, then it > sorts it self if it is an associative group. Ie.. from inner most group > to outer most group but only the associative ones. But you seem to fix behaviour together with an operation i.e. declaring that __mul__ is commutative. But in a general case you might have elements that commute, others that anti-commute ( i.e. a*b = -b*a ) and again others where no special rule is provided i.e. they simply don't commute. But much worse than this the definition of the operations __add__, __mul__ etc. use names of subclasses A,D explicitely(!) what means that the framework can't be extended by inheritance of A,D,M etc. This is not only bad OO style but customizing operations ( i.e. making __mul__ right associative ) for certain classes is prevented this way. One really has to assume a global behaviour fixed once as a class attribute. > > Playing with it further I get the following outputs. > > ( The parenthesis surround a group that is associated to the operation. > This is the same idea/suggestion I first proposed, it's just been > developed a little further along.) > > > b+a+2 = (2+a+b) <- addition group > > a*(b+45+23) = ((68+b)*a) <- addition group within multiply group > > a-4-3-7+b = ((a-14)+b) <- sub group within add group > > c*b-d*a+2 = (2+((b*c)-(a*d))) <- mults within subs within adds > > 7*a*8*9+b = ((504*a)+b) > > a*(b+c) = ((b+c)*a) > > c*3*a*d*c*b*7*c*d*a = (21*a*a*b*c*c*c*d*d) I still don't see how you distinguish between factors that might commute and others that don't. I don't want a and b commute but c and d with all other elements. > d*b/c*a = (((b*d)/c)*a) > > (d*b)/(c*a) = ((b*d)/(a*c)) > > d*b-a/e+d+c = (((b*d)-(a/e))+c+d) > > a/24/2/b = (a/48/b) > > c**b**(4-5) = (c**(b**-1)) > > (d**a)**(2*b) = ((d**a)**(2*b)) If you have fun with those identities you might like to find simplifications for those expressions too: a*0 -> 0 a*1 -> a 1/a/b -> b/a a+b+a -> 2*a+b a/a -> 1 a**1 -> a etc. > The next step is to be able to convert groups to other groups; an > exponent group to a multiply group; a subtract group to an addition > group with negative prefix's.. and so on. > > That would be how expansion and simplifying is done as well as testing > equivalence of equations. > > if m*c**2 == m*c*c: > print "Eureka!" > > > > Mixing operators is not really a problem, but one has to make initial > > decisions ( e.g about associativity i.e. flattening the parse-tree ) > > and sub-algebra generation by means of inheritance: > > What do you mean by 'sub-algebra generation'? Partially what I described in the subsequent example: the target of the addition of two elements x,y of X is again in X. This is not obvious if one takes an arbitrary nonempty subset X of Expr. > >>>>a,b = seq(2,Expr) > >>>>type(a+b) > > > > <class '__main__.Expr'> > > > >>>>class X(Expr):pass > >>>>x,y = seq(2,X) > >>>>type(x+y) > > > > <class '__main__.X'> > > > > This is not particular hard. It is harder to determine correspondence > > rules between operations on different levels. On subalgebras the > > operations of the parent algebra are induced. But what happens if one > > mixes objects of different algebras that interoperate with each other? > > It would be wise to find a unified approach to make distinctive > > operations visually distinctive too. Infix operators may be > > re-introduced just for convenience ( e.g. if we can assume that all > > algebras supporting __mul__ that are relevant in some computation have > > certain properties e.g. being associative ). > > Different algebras would need to be able to convert themselves to some > common representation. Then they would be able to be mixed with each > other with no problem. Well, it is a problem not only of representation. You might have three algebras A,B,C each providing a different multiplication operator and also interoperation capabilities: A*B = B*A may hold but (A,*) is not associative and neither A nor B interoperates with C i.e. an operation C*A or C*B is not defined. > Or an operation on an algebra group could just accept it as a unique > term, and during an expansion process it could convert it self (and it's > members) to the parents type. That would take a little more work, but I > don't see any reason why it would be especially difficult. > > Using that methodology, an equation with mixed algebra types could be > expanded as much as possible, then reduced back down again using a > chosen algebra or the one that results in the most concise representation. Maybe you should simply do that. > > > ########################################################################## > > > > After thinking about M ( or Expr ;) a little more I come up with a > > solution of the problem of central elements of an algebra ( at least > > the identity element e is always central ) that commute with all other > > elements. > > What is a "central" element? I can see it involves a set, but the > context isn't clear. "Central" elements are exactly those that commute with all other elements. In In abelian groups they constitute the groups itself. In non-abelian groups they are subgroups ( the center always exist and is contains at least the unit element ). Since each group has a center one can make general assertions without considering elements individually. It is a common pattern of reasoning to abstract from concrete elements and rely on properties of classes of elements. Kay -- http://mail.python.org/mailman/listinfo/python-list
