Ordering Products

[Kay Schluehr]

Ron Adam wrote:
> 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

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

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:

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


##########################################################################

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.

Here is my approach:

# Define a subclass of list, that provides the same interface as list
and
# a customized sorting algorithm

import sets

class Factors(list):
    def __init__(self,li):
        list.__init__(self,li)
        self.elems   = sets.Set(li)   # raw set of factors used in the
__mul__
        self._center = ()             # storing central elements
commuting with
                                      # with all others

    def _get_center(self):
        return self._center

    def _set_center(self,center):
        Center = sets.Set(center)
        if not Center<=self.elems:
            raise ValueError,"Subset required"
        else:
            self._center = Center

    center = property(_get_center, _set_center)

    def __add__(self,li):
        return Factors(list.__add__(self,li))

    def sort(self):
        center = list(self.center)
        def commutator(x,y):
            if isinstance(x,(int,float,long)):  # numeral literals
should
                return -1                       # always commute
            if isinstance(y,(int,float,long)):
                return 1
            if x == y:
                return 0
            if x in center:
                if y in center:
                    if center.index(x)<center.index(y):   # induce an
aritrary
                        return -1                         # order on
central
                    else:                                 # elements by
center
                        return 1
                else:
                    return -1
            return 0
        list.sort(self,commutator)


# Define an associative multiplicative algebra

class M(object):
    def __init__(self, name=""):
        self.name = name
        self.factors = Factors([self])    # implement factor list as
Factors

    def _get_center(self):
        return self.factors.center

    def _set_center(self,center):
        self.factors.center = center

    center = property(_get_center, _set_center)

    def __mul__(self, other):
        p = M()
        if isinstance(other,M):
            other_factors = other.factors
        else:
            other_factors = Factors([other])
        p.factors = self.factors+other_factors
        return p

    def __rmul__(self,other):
        p = M()
        p.factors = 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])


>>> a,b,c,d = M("a"),M("b"),M("c"),M("d")
>>> y = c*3*a*d*c*b*7*c*d*a
>>> y
c*3*a*d*c*b*7*c*d*a

>>> y.center = (c,d)
>>> y.factors.sort()
>>> y
7*3*c*c*c*d*d*a*b*a


Regards,
Kay