Ordering Products

[Ron Adam]

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)