Ordering Products

[Ron Adam]

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[0])
     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