Inverting permutations in Python

Question

I'm new to programming, and I'm trying to write a Python function to find the inverse of a permutation on {1,2,3,...,n} using the following code:

def inv(str):
    result = []
    i = list(str).index(min(list(str)))
    while min(list(str)) < len(list(str)) + 1:
        list(str)[i : i + 1] = [len(list(str)) + 1]
        result.append(i + 1)
    return result

However, when I try to use the function, inv('<mypermutation>') returns []. Am I missing something? Is Python skipping over my while loop for some syntactical reason I don't understand? None of my google and stackoverflow searches on topics I think of are returning anything helpful.

I tried renaming 'str' as 'permutation' and it still returned '[]'. Any other tips? — Fingolfin
– Fingolfin, Commented Feb 7, 2012 at 23:44
@Fingolfin: Oh, wait, are you literally executing inv('<mypermutation>')? Then the while conditions compares a string to an integer, which might have a False result, depending on the version the Python you use. In Python 3, for example, you'll get an error. — Reinstate Monica
– Reinstate Monica, Commented Feb 8, 2012 at 0:13
Fingolfin, I think you need to show a literal, unmodified example of how you call this function to help people figure this out. — David Z
– David Z, Commented Feb 8, 2012 at 0:27

d.b · Accepted Answer · 2021-04-30 23:15:43Z

24

Other answers are correct, but for what it's worth, there's a much more performant alternative using numpy:

inverse_perm = np.argsort(permutation)

EDIT: and the fourth function below is even faster.

Timing code:

def invert_permutation_list_scan(p):
    return [p.index(l) for l in range(len(p))]

def invert_permutation_list_comp(permutation):
    return [i for i, j in sorted(enumerate(permutation), key=lambda i_j: i_j[1])]

def invert_permutation_numpy(permutation):
    return np.argsort(permutation)

def invert_permutation_numpy2(permutation):
    inv = np.empty_like(permutation)
    inv[permutation] = np.arange(len(inv), dtype=inv.dtype)
    return inv

x = np.random.randn(1000)
perm = np.argsort(x)
permlist = list(perm)
assert np.array_equal(invert_permutation_list_scan(permlist), invert_permutation_numpy(perm))
assert np.array_equal(invert_permutation_list_comp(perm), invert_permutation_numpy(perm))
assert np.array_equal(invert_permutation_list_comp(perm), invert_permutation_numpy2(perm))
%timeit invert_permutation_list_scan(permlist)
%timeit invert_permutation_list_comp(perm)
%timeit invert_permutation_numpy(perm)
%timeit invert_permutation_numpy2(perm)

Results:

82.2 ms ± 7.28 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)
479 µs ± 9.19 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
18 µs ± 1.17 µs per loop (mean ± std. dev. of 7 runs, 100000 loops each)
4.22 µs ± 388 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

edited Apr 30, 2021 at 23:15

answered Apr 17, 2019 at 23:16

d.b

5031 gold badge5 silver badges10 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

VF1 Over a year ago

Well, if you're going for speed, then you can do less work: . ``` def invert_permutation_numpy2(permutation): x = np.empty_like(permutation) x[permutation] = np.arange(len(permutation), dtype=permutation.dtype) return x ``` . On the mini-benchmarks it beats numpy sorting 10-20x

d.b Over a year ago

@VF1 Nice. I've edited my answer to include this even faster function.

abukaj Over a year ago

I think np.arange(len(permutation))[np.argsort(permutation)] equals np.argsort(permutation).

d.b Over a year ago

Good catch. Fixed!

Reinstate Monica · Accepted Answer · 2012-02-07 23:54:16Z

12

If you only want the inverse permutation, you can use

def inv(perm):
    inverse = [0] * len(perm)
    for i, p in enumerate(perm):
        inverse[p] = i
    return inverse

perm = [3, 0, 2, 1]
print(inv(perm))
for i in perm:
    print(inv(perm)[i])

[1, 3, 2, 0]
0
1
2
3

answered Feb 7, 2012 at 23:54

Reinstate Monica

4,7531 gold badge27 silver badges36 bronze badges

Comments

Christian Borgelt · Accepted Answer · 2020-07-03 12:32:20Z

4

I believe the best way to invert a permutation perm is

pinv = sorted(range(len(perm)), key=perm.__getitem__)

This avoids repeated calls to .index() (as in the answer by SeF), which may not be very efficient (quadratic time complexity, while sorting should only take O(n log n)).

Note, however, that this yields as a result a permutation of {0,1,...n-1}, regardless of whether the input was a permutation of {0,1,...,n-1} or of {1,2,...,n} (the latter is what is stated in the question). If the output is supposed to be a permutation of {1,2,...,n}, each element of the result has to be increased by one, for example, like this:

pinv = [i+1 for i in sorted(range(len(perm)), key=perm.__getitem__)]

answered Jul 3, 2020 at 12:32

Christian Borgelt

1195 bronze badges

Comments

Louis Maddox · Accepted Answer · 2019-11-12 07:57:19Z

3

Just since no one has recommended it here yet, I think it should be mentioned that SymPy has an entire combinatorics module, with a Permutation class:

from sympy.combinatorics import Permutation
o = [3, 0, 2, 1]
p = Permutation(o)
inv = p.__invert__()
print(inv.array_form) # [1, 3, 2, 0]

Using the SymPy class gives you access to a whole lot of other useful methods, such as comparison between equivalent permutations with ==.

You can read the sympy.combinatorics.Permutation source code here.

Other than that, I would recommend the answer on this page using np.arange and argsort.

answered Nov 12, 2019 at 7:57

Louis Maddox

5,6756 gold badges44 silver badges69 bronze badges

Comments

SeF · Accepted Answer · 2019-12-20 11:37:06Z

2

Maybe there is a shorter way:

def invert(p):
    return [p.index(l) for l in range(len(p))]

so that:

perm = [3, 0, 2, 1]; print(invert(perm))

returns

[1,3,2,0]

edited Dec 20, 2019 at 11:37

answered Apr 18, 2018 at 17:06

SeF

4,2993 gold badges32 silver badges44 bronze badges

1 Comment

Maxim Over a year ago

Note that this is inefficient, O(len(p) ^ 2) in time.

Fingolfin · Accepted Answer · 2012-02-08 21:22:03Z

1

Correct me if I have this wrong, but I think the problem with my code comes when I change str to a list: str is a string, and list(str) is a list of string elements. However, since string elements can't be numerically compared to numbers, the code fails to produce a result (other than []).

answered Feb 8, 2012 at 21:22

Fingolfin

1331 gold badge1 silver badge6 bronze badges

Comments

kjo · Accepted Answer · 2017-01-21 17:56:09Z

1

A "functional style" version:

def invert_permutation(permutation):
    return [i for i, j in sorted(enumerate(permutation), key=lambda (_, j): j)]

Basically, sorting the indices i of the permutation by their values j in the permutation yields the desired inverse.

p = [2, 1, 5, 0, 4, 3]

invert_permutation(p)
# [3, 1, 0, 5, 4, 2]

# inverse of inverse = identity
invert_permutation(invert_permutation(p)) == p
# True

edited Jan 21, 2017 at 17:56

answered Jan 21, 2017 at 17:50

kjo

35.7k56 gold badges167 silver badges294 bronze badges

Collectives™ on Stack Overflow

Inverting permutations in Python

7 Answers 7

4 Comments

Comments

Comments

Comments

1 Comment

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

7 Answers 7

4 Comments

Comments

Comments

Comments

1 Comment

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related