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