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 -- http://mail.python.org/mailman/listinfo/python-list
