Ordering Products

[Kay Schluehr]

Ron Adam wrote:
> Kay Schluehr wrote:
> > Here might be an interesting puzzle for people who like sorting
> > algorithms ( and no I'm not a student anymore and the problem is not a
> > students 'homework' but a particular question associated with a
> > computer algebra system in Python I'm currently developing in my
> > sparetime ).
>
> <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