seemingly simple list indexing problem

[John Krukoff]

On Wed, 2008-07-30 at 12:06 -0700, Tobiah wrote:
> On Mon, 28 Jul 2008 23:41:51 -0700, iu2 wrote:
> 
> > On Jul 29, 3:59 am, John Machin <sjmac... at lexicon.net> wrote:
> >> On Jul 29, 8:10 am, John Krukoff <jkruk... at ltgc.com> wrote:
> >>
> >>
> >>
> >>
> >>
> >> > On Mon, 2008-07-28 at 16:24 -0500, Ervan Ensis wrote:
> >> > > My programming skills are pretty rusty and I'm just learning Python so
> >> > > this problem is giving me trouble.
> >>
> >> > > I have a list like [108, 58, 68].  I want to return the sorted indices
> >> > > of these items in the same order as the original list.  So I should
> >> > > return [2, 0, 1]
> >>
> >> > > For a list that's already in order, I'll just return the indices, i.e.
> >> > > [56, 66, 76] should return [0, 1, 2]
> >>
> >> > > Any help would be appreciated.
> >>
> >> > > --
> >> > >http://mail.python.org/mailman/listinfo/python-list
> >>
> >> > If your lists aren't so large that memory is an issue, this might be a
> >> > good place for a variation of decorate, sort, undecorate.
> >>
> >> > >>> listToSort = [ 108, 58, 68 ]
> >> > >>> decorated = [ ( data, index ) for index, data in
> >>
> >> > enumerate( listToSort ) ]>>> decorated
> >>
> >> > [(108, 0), (58, 1), (68, 2)]>>> result = [ None, ] * len( listToSort )
> >> > >>> for sortedIndex, ( ignoredValue, originalIndex ) in
> >>
> >> > enumerate( sorted( decorated ) ):
> >> > ...     result[ originalIndex ] = sortedIndex
> >> > ...>>> result
> >>
> >> > [2, 0, 1]
> >>
> >> Simpliciter:
> >>
> >>
> >>
> >> >>> data = [99, 88, 77, 88, 66]
> >> >>> [x[1] for x in sorted(zip(data, xrange(len(data))))]
> >> [4, 2, 1, 3, 0]
> >>
> >> Use case? Think data == database table, result == index ...- Hide quoted text -
> >>
> >> - Show quoted text -
> > 
> > I think it is wrong, using this on my data returns the wrong result
> >  data = [108, 58, 68, 108]
> >>>> [x[1] for x in sorted(zip(data, xrange(len(data))))]
> > [1, 2, 0, 3]
> 
> It looked wrong to me at first, but I think this is correct.
> The two largest numbers were at positions 0 and 3.  They come
> last in the result.  58 is the smallest, and was at position
> 1, which is the first in the result.
> 
> 
> 
> ** Posted from http://www.teranews.com **
> --
> http://mail.python.org/mailman/listinfo/python-list

It's wrong for the OP's sample, at least:
>>> data = [ 108, 58, 68 ]
>>> [x[1] for x in sorted(zip(data, xrange(len(data))))]
[1, 2, 0]

Which should be [2, 0, 1], according to the OP. I don't think the
problem description makes it clear until you stare at the example a bit,
but he's asking for a list where each value is the index in the sorted
list of the value in that position in the original list. What you've got
here is the index in the original list of the value that would be in
that location when sorted.

Clear as mud?

Stealing the quite clever __getitem__ as indirect key idea, this is as
short a solution as I've got:

>>> listToSort = [ 108, 58, 68 ]
>>> result = [ None, ] * len( listToSort )
>>> for sortedIndex, originalIndex in
enumerate( sorted( range( len( listToSort ) ), key =
listToSort.__getitem__ ) ):
...   result[ originalIndex ] = sortedIndex
... 
>>> result
[2, 0, 1]

I haven't benchmarked, but I bet it'd be better overall to do the range
sort in place, instead of with sorted. I'd like to be able to get rid of
the intermediate result initialization, but I haven't found a method
that's sane. This'd be my entry for obfuscated one-liner, though :)

>>> listToSort = [ 108, 58, 68 ]
>>> import operator
>>> map( operator.itemgetter( 1 ), sorted( dict( ( originalIndex,
sortedIndex ) for sortedIndex, originalIndex in
enumerate( sorted( xrange( len( listToSort ) ), key =
listToSort.__getitem__ ) ) ).items( ) ) )
[2, 0, 1]


-- 
John Krukoff <jkrukoff at ltgc.com>
Land Title Guarantee Company