a better way to invert a list?

[scattered]

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 = 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?

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. 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?

Thanks

 

[Ian Kelly]

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 = 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

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

 

[scattered]

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 = 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

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

 

[Raymond Hettinger]

[Ian Kelly]

Which is O(n).  If that is too verbose, you could also use a dictionary:

def invert(p):
    return dict(map(reversed, enumerate(p)))

def inv(p):
return dict(zip(p, itertools.count()))


Raymond

 

[Glazner]

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

invert([1, 2, 3, 1])

[None, 3, 1, 2] #blah

 

[scattered]

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

invert([1, 2, 3, 1])

[None, 3, 1, 2] #blah

I'm not sure if your post was meant to be serious, but if it was note
that [1,2,3,1] isn't a list which represents a permutation of
0,1,...,n-1 (where n is the length of the list). Ian Kelly's code
works correctly for input of the specified form.

 

[Peter Otten]

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

invert([1, 2, 3, 1])

[None, 3, 1, 2] #blah

1 occurs twice in [1, 2, 3, 1] which therefore doesn't describe a
permutation. In general a function has to be "bijective" to be invertable.
You can catch the problem with (untested)

def invert(p):
inverse = [None] * len(p)
for i, k in enumerate(p):
if inverse[k] is not None:
raise ValueError
inverse[k] = i
return inverse

 

[Paul Rubin]

def invert(p):
return [ j for (i,j) in sorted(zip(p,range(len(p))))]

return [j for i,j in sorted(enumerate(p), key=itemgetter(1))]

looks a little cleaner to me.

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?

Not as much. You could say something like

sorted(enumerate(p), key=lambda(_,j): j)

which gets the meaning across (it binds the symbol "_" though this
doesn't escape the lambda).

 

[Ian Kelly]

   In Haskell or ML, you can use patterns that contain wild
   cards that play a role in the pattern-matching but don't establishany
   binding. Can that be done in Python?

Not as much.  You could say something like

        sorted(enumerate(p), key=lambda(_,j): j)

which gets the meaning across (it binds the symbol "_" though this
doesn't escape the lambda).

That will just give you a SyntaxError. Implicit tuple unpacking was
removed in Python 3. It has to be done with an explicit assignment
statement now.