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.

Answer 1

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)

Answer 2

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