On Apr 5, 5:46 pm, Ian Kelly <ian.g.ke...@gmail.com> wrote: > 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))] >
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 -- http://mail.python.org/mailman/listinfo/python-list
