Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.python > #2673 > unrolled thread

a better way to invert a list?

Back to article view | Back to comp.lang.python

Contents

  a better way to invert a list? scattered <tooscattered@gmail.com> - 2011-04-05 14:17 -0700
    Re: a better way to invert a list? Ian Kelly <ian.g.kelly@gmail.com> - 2011-04-05 15:46 -0600
      Re: a better way to invert a list? scattered <tooscattered@gmail.com> - 2011-04-05 16:24 -0700
        Re: a better way to invert a list? Glazner <yoavglazner@gmail.com> - 2011-04-06 01:48 -0700
          Re: a better way to invert a list? scattered <tooscattered@gmail.com> - 2011-04-06 02:48 -0700
          Re: a better way to invert a list? Peter Otten <__peter__@web.de> - 2011-04-06 11:58 +0200
      Re: a better way to invert a list? Raymond Hettinger <python@rcn.com> - 2011-04-05 17:07 -0700
    Re: a better way to invert a list? Paul Rubin <no.email@nospam.invalid> - 2011-04-06 12:51 -0700
      Re: a better way to invert a list? Ian Kelly <ian.g.kelly@gmail.com> - 2011-04-06 14:08 -0600

#2673 — a better way to invert a list?

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?

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

[toc] | [next] | [standalone]

#2674

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

[toc] | [prev] | [next] | [standalone]

#2676

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

[toc] | [prev] | [next] | [standalone]

#2695

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

[toc] | [prev] | [next] | [standalone]

#2697

On Apr 6, 4:48 am, Glazner <yoavglaz...@gmail.com> wrote:
> > > 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.

[toc] | [prev] | [next] | [standalone]

#2698

Glazner wrote:

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

[toc] | [prev] | [next] | [standalone]

#2677

[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

[toc] | [prev] | [next] | [standalone]

#2718

scattered <tooscattered@gmail.com> writes:
> 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).

[toc] | [prev] | [next] | [standalone]

#2719

On Wed, Apr 6, 2011 at 1:51 PM, Paul Rubin <no.email@nospam.invalid> wrote:
>    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).

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.

[toc] | [prev] | [standalone]

Back to top | Article view | comp.lang.python

csiph-web