Ordering Products

[Kay Schluehr]

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