Ordering Products

[Ron Adam]

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.


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.

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)

  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))

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'?


>>>>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.

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.

> ##########################################################################
> 
> 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.


> Here is my approach:
> 
> # Define a subclass of list, that provides the same interface as list
> and
> # a customized sorting algorithm

It's not really that different from what I suggested.  And since my 
example is based on your first example.  It has a lot in common but the 
arrangement (organization) is a bit different.


> Regards,
> Kay


Here's the current version... It now handles more complex equations 
including exponents and perenthisized groupings.  It is fairly easy to 
extend which is one of the advantages of having each operation 
associated to a group.  It would be interesting to see what other 
opperators could be added to it.

Cheers,
Ronald Adam



#Factor - a single element or variable to be opperated on.
class F(list):
     Type = 'Factor'
     Commutative = False
     Symbol = ''
     Numerals = (int,float,long)
     def __init__(self,*x):
         list.__init__(self,x)
     def __add__(self, other):
         if isinstance(self,A):
             self.append(other)
             return self
         return A(self,other)
     def __radd__(self, other):
         if isinstance(self,A):
             self.append(other)
             return self
         return A(other,self)
     def __sub__(self, other):
         if isinstance(self,S):
             self.append(other)
             return self
         return S(self,other)
     def __rsub__(self, other):
         if isinstance(self,S):
             self.append(other)
             return self
         return S(other,self)
     def __mul__(self, other):
         if isinstance(self,M):
             self.append(other)
             return self
         return M(self,other)
     def __rmul__(self, other):
         if isinstance(self,M):
             self.append(other)
             return self
         return M(other,self)
     def __div__(self, other):
         if isinstance(self,D):
             self.append(other)
             return self
         return D(self,other)
     def __rdiv__(self, other):
         if isinstance(self,D):
             self.append(other)
             return self
         return D(other,self)
     def __pow__(self, other):
         return P(self,other)
     def __rpow__(self, other):
         return P(other,self)
     def __repr__(self):
         self._order_()
         if self.Type == 'Operator':
             self._simplify_()
             Pleft,Pright = '(',')'
         else:
             Pleft,Pright = '',''
         return Pleft+self.Symbol.join([str(x) for x in self])+Pright
     def _order_(self):
         for i in self:
             if hasattr(i, 'Commutative'):
                 if i.Commutative:
                     i._order_()
         if self.Commutative:
             self.sort()


## Operator classes durived from the Factor class.
#
# These group factors and other operator groups
# together in a group with a common opperator.

# Add
class A(F):
     Type = 'Operator'
     Commutative = True
     Symbol = '+'
     def _simplify_(self):
         #Was sorted first so all numerals shuold
         #be to the left.
         while ( len(self)>1
                     and isinstance(self[0],self.Numerals)
                     and isinstance(self[1],self.Numerals) ):
             self[0:2]=[self[0]+self[1]]

# Subtract
class S(F):
     Type = 'Operator'
     Commutative = False
     Symbol = '-'
     def _simplify_(self):
         while ( isinstance(self[0],self.Numerals)
                 and isinstance(self[1],self.Numerals) ):
             self[0:2] = [self[0]-self[1]]
         i = 1
         while i<len(self)-1:
             if ( isinstance(self[i],self.Numerals)
                     and isinstance(self[i+1],self.Numerals) ):
                 self[i:i+2]=[self[i]+self[i+1]]
             else:
                 i += 1

# Multipy
class M(F):
     Type = 'Operator'
     Commutative = True
     Symbol = '*'
     def _simplify_(self):
         # Was sorted first so all ints should
         # be to the left.
         while ( len(self)>1
                     and isinstance(self[0],self.Numerals)
                     and isinstance(self[1],self.Numerals) ):
             self[0:2]=[self[0]*self[1]]

# Divide
class D(F):
     Type = 'Operator'
     Commutative = False
     Symbol = '/'
     def _simplify_(self):
         while ( isinstance(self[0],self.Numerals)
                 and isinstance(self[1],self.Numerals) ):
             self[0:2] = [self[0]/self[1]]
         i = 1
         while i<len(self)-1:
             if ( isinstance(self[i],self.Numerals)
                     and isinstance(self[i+1],self.Numerals) ):
                 self[i:i+2]=[self[i]*self[i+1]]
             else:
                 i += 1

# Power
class P(F):
     Type = 'Operator'
     Commutative = False
     Symbol = '**'
     def _simplify_(self):
         # Todo
         pass



a = F('a')
b = F('b')
c = F('c')
d = F('d')
e = F('e')

print '\n b+a+2 =', b+a+2

print '\n a*(b+45+23) = ', a*(b+45+23)

print '\n a-4-3-7+b = ', a-4-3-7+b

print '\n c*b-d*a+2 =', c*b-d*a+2

print '\n 7*a*8*9+b =', 7*a*8*9+b

print '\n a*(b+c) =', a*(b+c)

print '\n c*3*a*d*c*b*7*c*d*a =', c*3*a*d*c*b*7*c*d*a

print '\n d*b/c*a =', d*b/c*a

print '\n (d*b)/(c*a) =', (d*b)/(c*a)

print '\n d*b-a/e+d+c =', d*b-a/e+d+c

print '\n a/24/2/b =', a/24/2/b

print '\n c**b**(4-5) =', c**b**(4-5)

print '\n (d**a)**(2*b) =', (d**a)**(2*b)