a better way to invert a list?

[Ian Kelly]

On Tue, Apr 5, 2011 at 3:17 PM, scattered <tooscattered 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))]

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

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