Re: Ordering Products
- From: "Kay Schluehr" <kay.schluehr@xxxxxxx>
- Date: 17 Jul 2005 22:31:04 -0700
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
.
- Follow-Ups:
- Re: Ordering Products
- From: Ron Adam
- Re: Ordering Products
- References:
- Ordering Products
- From: Kay Schluehr
- Re: Ordering Products
- From: Ron Adam
- Ordering Products
- Prev by Date: Re: Who uses input()? [was Re: question on "input"]
- Next by Date: Re: list implementation
- Previous by thread: Re: Ordering Products
- Next by thread: Re: Ordering Products
- Index(es):
Relevant Pages
|
