Velocity Reviews > Ordering Products

Ordering Products

Guest
Posts: n/a

 07-19-2005
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)
return A(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

Kay Schluehr
Guest
Posts: n/a

 07-19-2005
> 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)
> return A(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)ass
>>> 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 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

Kay Schluehr
Guest
Posts: n/a

 07-19-2005
Diez B.Roggisch wrote:
> > I have to admit that I don't understand what you mean with the
> > 'constant parts' of an expression?

>
> >From what I percieved of your example it seemed to me that you wanted to

> evaluate the constants like 7*9 first, so that an expression like
>
> a * 7 * 9 * b
>
> with variables a,b is evaluated like this:
>
> a * 63 * b
>
> So my suggestion was simply to make the *-operator more precedent when
> in between two constants. What I mean with constants here are of course
> integer/float literals. The concept of a differing operator precedence
> can be extended to arbitray elements when their types are known - which
> should be possible when variable values are known at parsing
> time.

O.K.

>
> > The associativity of __mul__ is trivially fullfilled for the dummy
> > class M if an additional __eq__ method is defined by comparing factor
> > lists because those lists are always flat:

>
> I don't care about that, as my approach deosn't use python's built-in parser
> - it can't, as that wouldn't allow to re-define operator precedence.

Diez, I try not to care too much about global operator precedence of
builtin infix operators. The hard problems in designing a CAS beyond
Mathematica are related to a bunch of interoperating algebras all
defining their own operations. Finally only local precedences exist
that are characteristic for certain patterns of expressions with a lot
of tangled operators ( e.g. 'geometric algebra' with vector products,
wedge products, inner products, additions and subtractions ). I don't
want a system defining a syntactically extendable language with 10
custom punctuations per module that no one ( at least not me ) can
remind and which looks as awkward as regular expressions.

> What you do is to
> simply collect the factors as list. But what you need (IMHO) is a parsing
> tree (AST) that reflects your desired behaviour by introducing a different
> precedence thus that the expression
>
> a * 7 *9 * b
>
> is not evaluated like
>
> ((a*7)*9)*b
>
> (which is a tree, and the standard way of evaluationg due to built-in parsers
> precedence rules) but as
>
> a*(7*9)*b
>
> which is also a tree.

Yes, but I tend to use __mul__ just for convenience. It is reflecting
an associative and non-commutative operator whereas __add__ is a
convenient way to fix an associative and commutative operator. In an
idealized mathematical interpretation they represent nothing specific
but as language elements they shall be fixed somehow.

For more general operations one may define functional operators e.g.
r_assoc and l_assoc where following (in)equations hold:

l_assoc(a,b,c) == l_assoc(l_assoc(a,b),c)
l_assoc(a,b,c) != l_assoc(a, l_assoc(b,c))

r_assoc(a,b,c) == r_assoc(a,r_assoc(b,c))
r_assoc(a,b,c) != r_assoc(r_assoc(a,b),c)

This kind of pattern can be used to define rules about l_assoc and
r_assoc.

Nevertheless, there is no loss of generality. The system lacks
prevention from deriving some class providing __mul__ and overwrite the
implementation of __mul__ using l_assoc. People may do this on their
own risk.

Kay

Guest
Posts: n/a

 07-19-2005
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 ..."

"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)ass
>>>>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,

#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)
if isinstance(self,A):
self.append(other)
return self
return A(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.

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)

Kay Schluehr
Guest
Posts: n/a

 07-20-2005
> 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 ..."
>
>
> "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)ass
> >>>>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

Guest
Posts: n/a

 07-20-2005
Kay Schluehr wrote:
>
>> Kay Schluehr wrote:

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

True.. but I think it's not predictable which response you will get
from an individual you aren't familiar with. I prefer positive
reinforcement over negative provocation myself.

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

I don't know if it's bad OO style because I chose a flatter model.
Your original question wasn't "what would be the best class structure to
use where different algebra's may be used". It was how can sorting be
done to an expression with constraints. And you gave an example which
set __mul__ as associative as well.

So this is a different problem. No use trying to point that what I did
doesn't fit this new problem, it wasn't suppose to.

I'm not sure what the best class structure would be. With the current
example, I would need to copy and edit F and it's associated sub
class's to create a second algebra type, F2, A2, M2.. etc. Not the best
solution to this additional problem which is what you are pointing out I
believe.

So... We have factors (objects), groups (expressions), and algebras
(rules), that need to be organized into a class structure that can
be extended easily.

Does that describe this new problem adequately? I'm not sure what the
best, or possible good solutions would be at the moment. I'll have to

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

In my example factors don't commute. They are just units, however
factors within a group unit may commute because a group is allowed to
commute factors if the operation the group is associated to is commutable.

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

Already did a few of those. Some of these involve changing a group into
a different group which was a bit of a challenge since an instance can't
magically change itself into another type of instance, so the parent
group has to request the sub-group to return a simplified or expanded
instance, then the parent can replace the group with the new returned
instance.

a*a*a -> a**3 change from a M group to a P group.
a*0 -> 0 change from a M group to an integer.
a*1 -> a change from a M group to a F unit.
a+b+a -> 2*a+b change a A subgroup to a M group.
a/a -> change a D group to an integer.
a**1 -> change a P group to a M group to a F unit.

Some of those would be done in the simplify method of the group. I've
added an expand method and gotten it to work on some things also.

a*b**3 -> a*b*b*b
c*4 -> c+c+c+c

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

Would that be similar to the simultaneous equation below?

z = x+y <- term x+y is z
x = a*z+b <- z is in term x
x = a(x+y)+b <- x is again in x (?)

I think this would be...

>>> x, y = F('x'), F('y')
>>> z = x+y
>>> x = a*z+b
>>> x

(((x+y)*a)+b)

This wouldn't actually solve for x since it doesn't take into account
the left side of the = in the equation. And it would need an eval
method to actually evaluated it. eval(str(expr)) does work if all the
factors are given values first.

Cheers,
Ron