Ordering Products
Ron Adam
rrr at ronadam.com
Sun Jul 17 20:51:04 CEST 2005
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)
More information about the Python-list
mailing list