seemingly simple list indexing problem

[John Krukoff]

On Mon, 2008-07-28 at 16:00 -0700, iu2 wrote:
> On Jul 29, 12: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]
> >
> > --
> > John Krukoff <jkruk... at ltgc.com>
> > Land Title Guarantee Company
> 
> Inspired by your idea and the above one, here is another try:
> 
> >>> a0 = [108, 58, 68, 108, 58]
> >>> a1 = [(x, y) for x, y in enumerate(a0)]

You know this line is a no-op, right?

> >>> a1
> [(0, 108), (1, 58), (2, 68), (3, 108), (4, 58)]
> >>> a2 = sorted(a1, lambda x, y: cmp(x[1], y[1]))

If you're going to do the unpacking here for the sort, just use
enumerate directly. Since this is a simple case, should use the key
parameter instead of the cmp parameter for speed. Can also use the
operator module to avoid a bit of lambda overhead:

>>> import operator
>>> a2 = sorted( enumerate( a0 ), key = operator.itemgetter( 1 ) )

> >>> a2
> [(1, 58), (4, 58), (2, 68), (0, 108), (3, 108)]
> >>> a3 = [a2.index(x) for x in a1]
> >>> a3
> [3, 0, 2, 4, 1]
> 
> The idea is to make each item unique (by making it a tuple), and then
> apply the naive solution.
> 
> --
> http://mail.python.org/mailman/listinfo/python-list

Using index is still kinda evil, due to the exponential time required
since you're rescanning half the list (on average) to find each index
value.

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