a better way to invert a list?

[scattered]

On Apr 5, 5:46 pm, Ian Kelly <ian.g.ke... at gmail.com> wrote:
> On Tue, Apr 5, 2011 at 3:17 PM, scattered <tooscatte... at gmail.com> wrote:
> > Greetings,
>
> > I've been playing around (in Python 3.1) with permutations of
> > 0,1,...,n-1, represented by lists, p, of length n, where p[i] = the
> > image of i under the permutation. I wanted to be able to calculate the
> > inverse of such a permutation, and came up with the following succint
> > but not quite readable function:
>
> > def invert(p):
> >        return [ j for (i,j) in sorted(zip(p,range(len(p))))]
>
> > I rejected the obvious [p.index(i) for i in range(len(p))] since that
> > seems an inefficient way to sort. Is there a better way to do this?
>
> Instead of zipping up range(len(p)), you could use the more Pythonic enumerate:
>
> def invert(p):
>     return [i for (i, j) in sorted(enumerate(p), key=operator.itemgetter(1))]
>

Seems a bit kludgy - isn't their any more direct way to sort by the
second element in a list of tuples? I gather that this is one area
where Python 3 differs from earlier Pythons - but I never had much
experience with Python 2 to compare it with.

> The main advantage here is that it will accept an iterator for p, not
> just a sequence.  But it's still O(n log n ) due to the sort.  More
> efficient would be:
>
> def invert(p):
>     inverse = [None] * len(p)
>     for (i, j) in enumerate(p):
>         inverse[j] = i
>     return inverse

Elegant. This seems like the best solution, although it isn't as much
fun to write as a "one-liner". Thanks

> Which is O(n).  If that is too verbose, you could also use a dictionary:
>
> def invert(p):
>     return dict(map(reversed, enumerate(p)))
>
> But the disadvantage here is that if you want to iterate over the
> result in order, you're back to either having to sort it or doing
> something ugly like this:
>
> q = invert(p)
> for i in range(len(q)):
>     # Do something with q[i]
>
> > Another question about my code: What is more idiomatic, [ j for (i,j)
> > in ...]   or [ x[1] for x in ... ]? I find the former more readable.
> > But it makes bindings for i and doesn't use them - which can't be very
> > efficient.
>
> I don't know of any reason to prefer one over the other.  One
> convention for unpacking values that aren't used is to name the
> variable '_'.  But this doesn't help efficiency at all; it's just a
> convention to inform somebody reading the code that the value is
> ignored.
>
> > In Haskell or ML, you can use patterns that contain wild
> > cards that play a role in the pattern-matching but don't establish any
> > binding. Can that be done in Python?
>
> No, unfortunately.
>
> Cheers,
> Ian