rrr at ronadam.com
Mon Jul 18 11:36:03 CEST 2005
Kay Schluehr wrote:
> Ron Adam wrote:
>>Kay Schluehr wrote:
>>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.
I want to establish the sort order at the beginning of the sort process
instead of using many external compares during the sort process. Using
a preprocessed sort key seems like the best way to do that. How it's
generated doesn't really matter. And of course a set of standard
defaults could be built in.
>>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.
The advantage of doing it as above would be the sort could be done
entirely in C and not need to call a python compare function on each
item. It would be interesting to see if and how much faster it would
be. I'm just not sure how to do it yet as it's a little more
complicated than using integer values.
>>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 ).
I'm played around with your example a little bit and think I see how it
should work... (partly guessing) You did some last minute editing so M
and Expr were intermixed.
It looks to me that what you need to do is have the expressions stored
as nested lists and those can be self sorting. That can be done when
init is called I think, and after any operation.
You should be able to add addition without too much trouble too.
a*b -> factors [a],[b] -> [a,b] You got this part.
c+d -> sums [c],[d] -> [c,d] Need a sums type for this.
a*b+c*d -> sums of factors -> [[a,b],[c,d]]
This would be sorted from inner to outer.
(a+b)*(b+c) -> factors of sums -> [[a,b],[c,d]]
Maybe you can sub class list to create the different types? Each list
needs to be associated to an operation.
The sort from inner to outer still works. Even though the lists
represent different operations.
You can sort division and minus if you turn them into sums and factors
1-2 -> sums [1,-2]
3/4 -> factors [3,1/4] ? hmmm... I don't like that.
Or that might be...
3/4 -> factor , divisor  -> [3,]
So you need a divisor type as a subtype of factor. (I think)
You can then combine the divisors within factors and sort from inner to
(a/b)*(c/e) -> [a,[b],c,[e]] -> [a,c,[b,e]]
Displaying these might take a little more work. The above could get
Which I think is what you want it to do.
Just a few thoughts. ;-)
More information about the Python-list