Ordering Products

[Ron Adam]

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.
> 
> 
> Exactly.

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 ).
> 
> Kay

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.

Then...

    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 
first.

    1-2   ->  sums [1,-2]

    3/4   ->  factors [3,1/4]   ?  hmmm...  I don't like that.

Or that might be...

    3/4   ->  factor [3], divisor [4]  ->  [3,[4]]


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 
outer.

    (a/b)*(c/e)  ->  [a,[b],c,[e]]  -> [a,c,[b,e]]

Displaying these might take a little more work.  The above could get 
represented as...

    (a*c)/(b*e)

Which I think is what you want it to do.


Just a few thoughts.  ;-)


Cheers,
Ron