On Tue, Apr 5, 2011 at 3:17 PM, scattered <tooscatte...@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 -- http://mail.python.org/mailman/listinfo/python-list