Ordering Products

Discussion in 'Python' started by Kay Schluehr, Jul 17, 2005.

  1. Kay Schluehr

    Kay Schluehr Guest

    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:

    class Expr:
    def __init__(self, name=""):
    self.name = name
    self.factors = [self]

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

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

    One can create arbitrary products of Expr objects ( and mixing numbers
    into the products ):

    >>> a,b,c = Expr("a"),Expr("b"),Expr("c")
    >>> a*b

    a*b
    >>> 7*a*8*9

    7*a*8*9

    The goal is to evaluate such products and/or to simplify them.

    For expressions like

    >>> x = 7*a*8*9


    this might be easy, because we just have to sort the factor list and
    multiply the numbers.

    >>> x.factors.sort()
    >>> x

    a*7*8*9

    -> a*504

    This can be extended to arbitrary products:

    >>> x = 7*a*b*a*9
    >>> x.factors.sort()
    >>> x

    a*a*b*7*9

    -> (a**2)*b*63

    Now lets drop the assumption that a and b commute. More general: let be
    M a set of expressions and X a subset of M where each element of X
    commutes with each element of M: how can a product with factors in M be
    evaluated/simplified under the condition of additional information X?

    It would be interesting to examine some sorting algorithms on factor
    lists with constrained item transpositions. Any suggestions?

    Regards,
    Kay
     
    Kay Schluehr, Jul 17, 2005
    #1
    1. Advertising

  2. Kay Schluehr

    Ron Adam Guest

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


    <folded>

    >>>>x = 7*a*b*a*9
    >>>>x.factors.sort()
    >>>>x

    >
    > a*a*b*7*9
    >
    > -> (a**2)*b*63
    >
    > Now lets drop the assumption that a and b commute. More general: let be
    > M a set of expressions and X a subset of M where each element of X
    > commutes with each element of M: how can a product with factors in M be
    > evaluated/simplified under the condition of additional information X?
    >
    > It would be interesting to examine some sorting algorithms on factor
    > lists with constrained item transpositions. Any suggestions?
    >
    > Regards,
    > Kay


    Looks interesting Kay.

    I think while the built in sort works as a convenience, you will need to
    write your own more specialized methods, both an ordering (parser-sort),
    and simplify method, and call them alternately until no further changes
    are made. (You might be able to combine them in the sort process as an
    optimization.)

    A constrained sort would be a combination of splitting (parsing) the
    list into sortable sub lists and sorting each sub list, possibly in a
    different manner, then reassembling it back. And doing that possibly
    recursively till no further improvements are made or can be made.


    On a more general note, I think a constrained sort algorithm is a good
    idea and may have more general uses as well.

    Something I was thinking of is a sort where instead of giving a
    function, you give it a sort key list. Then you can possibly sort
    anything in any arbitrary order depending on the key list.

    sort(alist, [0,1,2,3,4,5,6,7,8,9]) # Sort numbers forward
    sort(alist, [9,8,7,6,5,4,3,2,1,0]) # Reverse sort
    sort(alist, [1,3,5,7,9,0,2,4,6,8]) # Odd-Even sort
    sort(alist, [int,str,float]) # sort types

    These are just suggestions, I haven't worked out the details. It could
    probably be done currently with pythons built in sort by writing a
    custom compare function that takes a key list. How fine grained the key
    list is is also something that would need to be worked out. Could it
    handle words and whole numbers instead of letters and digits? How does
    one specify which? What about complex objects?


    Here's a "quick sort" function that you might be able to play with..
    There are shorter versions of this, but this has a few optimizations added.

    Overall it's about 10 times slower than pythons built in sort for large
    lists, but that's better than expected considering it's written in
    python and not C.

    Cheers,
    Ron



    # Quick Sort
    def qsort(x):
    if len(x)<2:
    return x # Nothing to sort.

    # Is it already sorted?
    j = min = max = x[0]
    for i in x:
    # Get min and max while checking it.
    if i<min: min=i
    if i>max: max=i
    if i<j: # It's not sorted,
    break # so stop checking and sort.
    j=i
    else:
    return x # It's already sorted.

    lt = []
    eq = []
    gt = []

    # Guess the middle value based on min and max.
    mid = (min+max)//2

    # Divide into three lists.
    for i in x:
    if i<mid:
    lt.append(i)
    continue
    if i>mid:
    gt.append(i)
    continue
    eq.append(i)

    # Recursively divide the lists then reassemble it
    # in order as the values are returned.
    return q(lt)+eq+q(gt)
     
    Ron Adam, Jul 17, 2005
    #2
    1. Advertising

  3. Kay Schluehr <kay.schluehr <at> gmx.net> writes:

    > Now lets drop the assumption that a and b commute. More general: let be
    > M a set of expressions and X a subset of M where each element of X
    > commutes with each element of M: how can a product with factors in M be
    > evaluated/simplified under the condition of additional information X?
    >
    > It would be interesting to examine some sorting algorithms on factor
    > lists with constrained item transpositions. Any suggestions?


    I don't think that sorting is the answer here.
    Firts of all IMHO you have to add an
    additional constraint - associativity of the operation in question
    So the problem could be reduced to making the constant
    parts be more associative than the non-constant parts.
    which you should be able to
    do with a parser. The BNF grammar could look like this:

    expr ::= v_expr "*" v_expr | v_expr
    v_expr ::= variable | c_expr
    c_expr ::= l_expr "*" literal | l_expr
    l_expr ::= literal | "(" expr ")"

    The trick is to create a stronger-binding multiplication operator on constants
    than on mixed
    expressions.

    This grammar is ambigue of course - so a LL(k) or maybe even LALR won't work.
    But earley's method
    implemented in spark should do the trick.
    If I find the time, I'll write an short implementation
    tomorrow.

    Diez
     
    Diez B.Roggisch, Jul 17, 2005
    #3
  4. Kay Schluehr

    Kay Schluehr Guest

    Diez B.Roggisch wrote:
    > Kay Schluehr <kay.schluehr <at> gmx.net> writes:
    >
    > > Now lets drop the assumption that a and b commute. More general: let be
    > > M a set of expressions and X a subset of M where each element of X
    > > commutes with each element of M: how can a product with factors in M be
    > > evaluated/simplified under the condition of additional information X?
    > >
    > > It would be interesting to examine some sorting algorithms on factor
    > > lists with constrained item transpositions. Any suggestions?

    >
    > I don't think that sorting is the answer here.
    > Firts of all IMHO you have to add an
    > additional constraint - associativity of the operation in question
    > So the problem could be reduced to making the constant
    > parts be more associative than the non-constant parts.
    > which you should be able to
    > do with a parser.


    Hi Diez,

    I have to admit that I don't understand what you mean with the
    'constant parts' of an expression?

    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:

    def __eq__(self, other):
    if isinstance(other,M):
    return self.factors == other.factors
    return False

    The sorting ( or better 'grouping' which can be represented by sorting
    in a special way ) of factors in question is really a matter of
    (non-)commutativity. For more advanced expressions also group
    properties are important:

    If a,b are in a center of a group G ( i.e. they commute with any
    element of G ) and G supplies an __add__ ( besides a __mul__ and is
    therefore a ring ) also a+b is in the center of G and (a+b)*c = c*(a+b)
    holds for any c in G.

    It would be nice ( and much more efficient ) not to force expansion of
    the product assuming distributivity of __add__ and __mul__ and
    factorization after the transposition of the single factors but
    recognizing immediately that a+b is in the center of G because the
    center is a subgroup of G.


    Regards,
    Kay
     
    Kay Schluehr, Jul 18, 2005
    #4
  5. Kay Schluehr

    Kay Schluehr Guest

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

    >
    > <folded>
    >
    > >>>>x = 7*a*b*a*9
    > >>>>x.factors.sort()
    > >>>>x

    > >
    > > a*a*b*7*9
    > >
    > > -> (a**2)*b*63
    > >
    > > Now lets drop the assumption that a and b commute. More general: let be
    > > M a set of expressions and X a subset of M where each element of X
    > > commutes with each element of M: how can a product with factors in M be
    > > evaluated/simplified under the condition of additional information X?
    > >
    > > It would be interesting to examine some sorting algorithms on factor
    > > lists with constrained item transpositions. Any suggestions?
    > >
    > > Regards,
    > > Kay

    >
    > Looks interesting Kay.


    I think so too :) And grouping by sorting may be interesting also for
    people who are not dealing with algebraic structures.

    > I think while the built in sort works as a convenience, you will need to
    > write your own more specialized methods, both an ordering (parser-sort),
    > and simplify method, and call them alternately until no further changes
    > are made. (You might be able to combine them in the sort process as an
    > optimization.)
    >
    > A constrained sort would be a combination of splitting (parsing) the
    > list into sortable sub lists and sorting each sub list, possibly in a
    > different manner, then reassembling it back. And doing that possibly
    > recursively till no further improvements are made or can be made.


    I think a comparison function which is passed into Pythons builtin
    sort() should be sufficient to solve the problem. I guess the
    comparison defines a total order on the set of elements defined by the
    list to sort.

    > On a more general note, I think a constrained sort algorithm is a good
    > idea and may have more general uses as well.
    >
    > Something I was thinking of is a sort where instead of giving a
    > function, you give it a sort key list. Then you can possibly sort
    > anything in any arbitrary order depending on the key list.
    >
    > sort(alist, [0,1,2,3,4,5,6,7,8,9]) # Sort numbers forward
    > sort(alist, [9,8,7,6,5,4,3,2,1,0]) # Reverse sort
    > sort(alist, [1,3,5,7,9,0,2,4,6,8]) # Odd-Even sort
    > sort(alist, [int,str,float]) # sort types


    Seems like you want to establish a total order of elements statically.
    Don't believe that this is necessary.

    > These are just suggestions, I haven't worked out the details. It could
    > probably be done currently with pythons built in sort by writing a
    > custom compare function that takes a key list.


    Exactly.

    > How fine grained the key
    > list is is also something that would need to be worked out. Could it
    > handle words and whole numbers instead of letters and digits? How does
    > one specify which? What about complex objects?


    In order to handle complex objects one needs more algebra ;)

    Since the class M only provides one operation I made the problem as
    simple as possible ( complex expressions do not exist in M because
    __mul__ is associative - this is already a reduction rule ).

    Kay
     
    Kay Schluehr, Jul 18, 2005
    #5
  6. Kay Schluehr wrote:

    >
    > Now lets drop the assumption that a and b commute. More general: let be
    > M a set of expressions and X a subset of M where each element of X
    > commutes with each element of M: how can a product with factors in M be
    > evaluated/simplified under the condition of additional information X?
    >
    > It would be interesting to examine some sorting algorithms on factor
    > lists with constrained item transpositions. Any suggestions?
    >


    Hello Kay,

    take this into account:
    Restrictions like commutativity, associative, distributive and flexibility
    laws don't belong neither to operands nor to operators themselves.
    Instead these are properties of fields (set of numbers with respect to a
    certain operation).
    For a famous example for a somewhat "alternative" behaviour look at the
    Octonions (discovered in 1843 by Graves and 1845 by Cayley), which are not
    associative with respect to addition and/or multiplication.
    (http://en.wikipedia.org/wiki/Octonions) or the Quarternions, which are
    non-commutative (http://en.wikipedia.org/wiki/Quaternion)

    Obviously, it's not correct to say: addition is associative, or, that
    multiplication is. With the same right, you could say, multiplication is
    not associative.
    With the same reasoning, we can show that it's not easy to generalize
    sorting, commutation, association or distribution mechanisms.

    Maybe it would be a very fascinating goal to solve your algorithmic approach
    in such a limited environment like the Quarternions.
    A solution for this set of numbers, if achieved in a clean, mathematically
    abstract way, should hold for most other numbers/fields too, natural and
    real included.

    I guess that the approach might be this way:
    - define/describe the fields which shall be handled
    - define/describe the rules which shall be supported
    - find methods to reduce sequences of operations to simple binary or unary
    operations (tokens) - this may introduce brackets and stacking mechanisms
    - a weighing algorithm might be necessary to distinguish between plain
    numbers and place holders (variables)
    - application of the distributivity (as far as possible) might help to find
    a rather flat representation and a base for reordering according to the
    weights of the individual sub-expressions

    Nevertheless, there are lots of commercial programs which do such sort of
    symbolic mathematics, and which would badly fail when it would come to such
    awkward fields like Quarternions/Octonions.


    Bernhard
     
    Bernhard Holzmayer, Jul 18, 2005
    #6
  7. > 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.

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

    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.

    > The sorting ( or better 'grouping' which can be represented by sorting
    > in a special way ) of factors in question is really a matter of
    > (non-)commutativity. For more advanced expressions also group
    > properties are important:


    No, IMHO associativity is the important thing here - if

    (a * 7) * 9

    yields a different solution than

    a *(7*9)

    your reordering can't be done - in the same way as re-arranging
    factors a*b to b*a only works if the commute - or, to put in in
    algebraic terms, the group is abelian.

    > If a,b are in a center of a group G ( i.e. they commute with any
    > element of G ) and G supplies an __add__ ( besides a __mul__ and is
    > therefore a ring ) also a+b is in the center of G and (a+b)*c = c*(a+b)
    > holds for any c in G.
    >
    > It would be nice ( and much more efficient ) not to force expansion of
    > the product assuming distributivity of __add__ and __mul__ and
    > factorization after the transposition of the single factors but
    > recognizing immediately that a+b is in the center of G because the
    > center is a subgroup of G.


    Well, you don't need to expand that product - the subexpression a+b is
    evaluated first. If you can sort of "cache" that evaluation's result because
    the expressions involved are of a constant nature, you can do so.

    The rason (a+b) is evaluated first (at least in the standard python parser,
    and in my proposed special parser) is that the parentheses ensure that.

    To sum things up a little: I propose not using the python built-in parser
    which results in you having to overload operators and lose control
    of precedence, but by introducing your own parser, that can do the
    trick of re-arranging the operators based on not only the "usual" precedence
    (* binds stronger than +), but by a type-based parser that can even change
    precedence of the same operator between different argument types is's
    applied to. That might sound complicated, but I think the grammar
    I gave in my last post shows the concept pretty well.

    regards,

    Diez
     
    Diez B.Roggisch, Jul 18, 2005
    #7
  8. Kay Schluehr

    Ron Adam Guest

    Kay Schluehr wrote:

    >
    > Ron Adam wrote:
    >
    >>Kay Schluehr wrote:


    >>On a more general note, I think a constrained sort algorithm is a good
    >>idea and may have more general uses as well.
    >>
    >>Something I was thinking of is a sort where instead of giving a
    >>function, you give it a sort key list. Then you can possibly sort
    >>anything in any arbitrary order depending on the key list.
    >>
    >> sort(alist, [0,1,2,3,4,5,6,7,8,9]) # Sort numbers forward
    >> sort(alist, [9,8,7,6,5,4,3,2,1,0]) # Reverse sort
    >> sort(alist, [1,3,5,7,9,0,2,4,6,8]) # Odd-Even sort
    >> sort(alist, [int,str,float]) # sort types

    >
    >
    > Seems like you want to establish a total order of elements statically.
    > Don't believe that this is necessary.


    I want to establish the sort order at the beginning of the sort process
    instead of using many external compares during the sort process. Using
    a preprocessed sort key seems like the best way to do that. How it's
    generated doesn't really matter. And of course a set of standard
    defaults could be built in.

    >>These are just suggestions, I haven't worked out the details. It could
    >>probably be done currently with pythons built in sort by writing a
    >>custom compare function that takes a key list.

    >
    >
    > Exactly.


    The advantage of doing it as above would be the sort could be done
    entirely in C and not need to call a python compare function on each
    item. It would be interesting to see if and how much faster it would
    be. I'm just not sure how to do it yet as it's a little more
    complicated than using integer values.

    >>How fine grained the key
    >>list is is also something that would need to be worked out. Could it
    >>handle words and whole numbers instead of letters and digits? How does
    >>one specify which? What about complex objects?

    >
    >
    > In order to handle complex objects one needs more algebra ;)
    >
    > Since the class M only provides one operation I made the problem as
    > simple as possible ( complex expressions do not exist in M because
    > __mul__ is associative - this is already a reduction rule ).
    >
    > Kay


    I'm played around with your example a little bit and think I see how it
    should work... (partly guessing) You did some last minute editing so M
    and Expr were intermixed.

    It looks to me that what you need to do is have the expressions stored
    as nested lists and those can be self sorting. That can be done when
    init is called I think, and after any operation.

    You should be able to add addition without too much trouble too.

    a*b -> factors [a], -> [a,b] You got this part.

    c+d -> sums [c],[d] -> [c,d] Need a sums type for this.

    Then...

    a*b+c*d -> sums of factors -> [[a,b],[c,d]]

    This would be sorted from inner to outer.

    (a+b)*(b+c) -> factors of sums -> [[a,b],[c,d]]

    Maybe you can sub class list to create the different types? Each list
    needs to be associated to an operation.

    The sort from inner to outer still works. Even though the lists
    represent different operations.

    You can sort division and minus if you turn them into sums and factors
    first.

    1-2 -> sums [1,-2]

    3/4 -> factors [3,1/4] ? hmmm... I don't like that.

    Or that might be...

    3/4 -> factor [3], divisor [4] -> [3,[4]]


    So you need a divisor type as a subtype of factor. (I think)


    You can then combine the divisors within factors and sort from inner to
    outer.

    (a/b)*(c/e) -> [a,,c,[e]] -> [a,c,[b,e]]

    Displaying these might take a little more work. The above could get
    represented as...

    (a*c)/(b*e)

    Which I think is what you want it to do.


    Just a few thoughts. ;-)


    Cheers,
    Ron
     
    Ron Adam, Jul 18, 2005
    #8
  9. Kay Schluehr

    Kay Schluehr Guest

    Bernhard Holzmayer schrieb:
    > Kay Schluehr wrote:
    >
    > >
    > > Now lets drop the assumption that a and b commute. More general: let be
    > > M a set of expressions and X a subset of M where each element of X
    > > commutes with each element of M: how can a product with factors in M be
    > > evaluated/simplified under the condition of additional information X?
    > >
    > > It would be interesting to examine some sorting algorithms on factor
    > > lists with constrained item transpositions. Any suggestions?
    > >

    >
    > Hello Kay,
    >
    > take this into account:
    > Restrictions like commutativity, associative, distributive and flexibility
    > laws don't belong neither to operands nor to operators themselves.
    > Instead these are properties of fields (set of numbers with respect to a
    > certain operation).
    > For a famous example for a somewhat "alternative" behaviour look at the
    > Octonions (discovered in 1843 by Graves and 1845 by Cayley), which are not
    > associative with respect to addition and/or multiplication.
    > (http://en.wikipedia.org/wiki/Octonions) or the Quarternions, which are
    > non-commutative (http://en.wikipedia.org/wiki/Quaternion)
    >
    > Obviously, it's not correct to say: addition is associative, or, that
    > multiplication is. With the same right, you could say, multiplication is
    > not associative.


    It was associative in the tiny example I presented. I did not mentioned
    to discuss the evolving structure of the whole CAS here in detail which
    would be better done in an own newsgroup once an early version is
    released.

    Maybe the setting of the original question should be made more precise:
    associative, non-commutative multiplicative groups.

    Handling non-associative algebras like Lie algebras is a completely
    different matter and I'm not even sure which one is the best way to
    represent operations in Python?

    Maye this way?

    >>> lie = Lie() # create an arbitrary Lie algebra (lie is again a class )
    >>> A,B = lie(),lie() # create two arbitrary elements of the Lie algebra
    >>> lie[A,B] # create the commutator of the lie algebra by overloading

    lie[A,B] # the __getitem__ method

    >>> lie[A,B] == -lie[-A,B]

    True

    If one wants to enforce assertions like

    >>> lie[r*A,B] == r*lie[A,B]

    True

    for certain elements r of some group acting on lie, one must refine
    creation of lie in the initial assignment statement e.g.

    >>> lie = Lie(V)


    where V is some vectorspace and the elements of lie are homomorphisms
    on V. V is created elsewhere. There are a lot of constraints induced by
    all the objects dynamically coupled together.

    > With the same reasoning, we can show that it's not easy to generalize
    > sorting, commutation, association or distribution mechanisms.
    >
    > Maybe it would be a very fascinating goal to solve your algorithmic approach
    > in such a limited environment like the Quarternions.


    No CAS can represent infinitely many different representations of
    quaternions. But it should not be to hard to deal with an algebra that
    represents admissable operations on quaternions in an abstract fashion.

    > A solution for this set of numbers, if achieved in a clean, mathematically
    > abstract way, should hold for most other numbers/fields too, natural and
    > real included.
    >
    > I guess that the approach might be this way:
    > - define/describe the fields which shall be handled
    > - define/describe the rules which shall be supported
    > - find methods to reduce sequences of operations to simple binary or unary
    > operations (tokens) - this may introduce brackets and stacking mechanisms
    > - a weighing algorithm might be necessary to distinguish between plain
    > numbers and place holders (variables)
    > - application of the distributivity (as far as possible) might help to find
    > a rather flat representation and a base for reordering according to the
    > weights of the individual sub-expressions
    >
    > Nevertheless, there are lots of commercial programs which do such sort of
    > symbolic mathematics, and which would badly fail when it would come to such
    > awkward fields like Quarternions/Octonions.


    If you take a look on Mathematica or Maple both programs seem to
    interpret pure symbols as members of an associative and commutative
    algebra:

    expand( (a+x)^2) -> a^2 + 2ax + x^2

    This works very fast and accurate but is mathematically too restricted
    for me. For doing more advanced stuff one needs to do a lot of
    programming in either language shipped with the CAS for creating new
    packages. But then I ask myself: why not doing the programming labor in
    Python and redesign and optimize the core modules of the CAS if
    necessary?

    Kay
     
    Kay Schluehr, Jul 18, 2005
    #9
  10. I see, you're sensitive for the difficulties which might arise.
    That's the thing I wanted to point out.
    Maybe I was looking too far forward...

    My first thought was to add attributes/qualifiers to the operands to improve
    the sorting.
    Then I realized that these attributes/qualifiers were related to the
    operators, since multiplication and division use the same operands, but
    while in one case it is associative and commutative, it isn't in the other.

    I agree that all this leads too far.
    But one thing creeps into my mind again:

    I guess you'll always need an inverse operation:
    A class which can handle multiplication will certainly require an inverse
    operation like division.

    Bernhard
     
    Bernhard Holzmayer, Jul 18, 2005
    #10
  11. Kay Schluehr

    Ron Adam Guest

    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
     
    Ron Adam, Jul 19, 2005
    #11
  12. Kay Schluehr

    Kay Schluehr Guest

    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
     
    Kay Schluehr, Jul 19, 2005
    #12
  13. Kay Schluehr

    Kay Schluehr Guest

    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
     
    Kay Schluehr, Jul 19, 2005
    #13
  14. Kay Schluehr

    Ron Adam Guest

    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,self.Numerals)
    and isinstance(self[i+1],self.Numerals) ):
    self[i:i+2]=[self+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,self.Numerals)
    and isinstance(self[i+1],self.Numerals) ):
    self[i:i+2]=[self*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)
     
    Ron Adam, Jul 19, 2005
    #14
  15. Kay Schluehr

    Kay Schluehr Guest

    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
     
    Kay Schluehr, Jul 20, 2005
    #15
  16. Kay Schluehr

    Ron Adam Guest

    Kay Schluehr wrote:
    > Ron Adam 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
    think about it a bit.


    >> 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
     
    Ron Adam, Jul 20, 2005
    #16
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. CodeMonkey
    Replies:
    0
    Views:
    429
    CodeMonkey
    Oct 11, 2005
  2. Edwin Naroska
    Replies:
    0
    Views:
    4,721
    Edwin Naroska
    Jul 8, 2003
  3. Edwin Naroska
    Replies:
    0
    Views:
    1,371
    Edwin Naroska
    Aug 29, 2003
  4. Edwin Naroska
    Replies:
    0
    Views:
    1,424
    Edwin Naroska
    Nov 28, 2003
  5. nbigaouette

    Z-Ordering (Morton ordering) question

    nbigaouette, Nov 5, 2009, in forum: C Programming
    Replies:
    2
    Views:
    2,317
Loading...

Share This Page