Tough sorting problem: or, I'm confusing myself

[Paul McGuire]

On Apr 9, 10:03 am, david jensen <dmj.... at gmail.com> wrote:
> Hi all,
>
> I'm trying to find a good way of doing the following:
>
> Each n-tuple in combinations( range( 2 ** m ), n ) has a corresponding
> value n-tuple (call them "scores" for clarity later). I'm currently
> storing them in a dictionary, by doing:
>
> ----
> res={}
> for i in itertools.combinations( range( 2**m ) , n):
>     res[ i ] = getValues( i )    # getValues() is computationally
> expensive
> ----
>
> For each (n-1)-tuple, I need to find the two numbers that have the
> highest scores versus them. I know this isn't crystal clear, but
> hopefully an example will help: with m=n=3:
>
> Looking at only the (1, 3) case, assuming:
> getValues( (1, 2, 3) ) == ( -200, 125, 75 )    # this contains the
> highest "other" score, where 2 scores 125
> getValues( (1, 3, 4) ) == ( 50, -50, 0 )
> getValues( (1, 3, 5) ) == ( 25, 300, -325 )
> getValues( (1, 3, 6) ) == ( -100, 0, 100 )    # this contains the
> second-highest, where 6 scores 100
> getValues( (1, 3, 7) ) == ( 80, -90, 10  )
> getValues( (1, 3, 8) ) == ( 10, -5, -5 )
>
> I'd like to return ( (2, 125), (6, 100) ).
>
> The most obvious (to me) way to do this would be not to generate the
> res dictionary at the beginning, but just to go through each
> combinations( range( 2**m), n-1) and try every possibility... this
> will test each combination n times, however, and generating those
> values is expensive. [e.g. (1,2,3)'s scores will be generated when
> finding the best possibilities for (1,2), (1,3) and (2,3)]
>

Add a memoizing decorator to getValues, so that repeated calls will do
lookups instead of repeated calculations.

-- Paul