Practice Now
numpy
permutation
array inversion
python programming
data manipulation

How to invert a permutation array in numpy

ML System Design practice on Codemia

Design recommenders, ranking systems and training pipelines the way ML interviews actually ask for them, with worked solutions.

Practice ML system design
Data ScienceData StructuresMath for ProgrammersPython

Introduction

Inverting a permutation array means finding the array that undoes the permutation — if P[i] = j, then the inverse Q[j] = i. In NumPy, the most efficient method is np.argsort(P), which returns the indices that would sort P, effectively computing the inverse permutation. An alternative is direct index assignment: Q[P] = np.arange(len(P)). Both approaches run in O(n) or O(n log n) time and are vectorized.

What Is a Permutation Inverse?

python
1import numpy as np
2
3# Permutation: position i maps to position P[i]
4P = np.array([2, 0, 1, 4, 3])
5# P says: element at position 0 goes to position 2
6#         element at position 1 goes to position 0
7#         element at position 2 goes to position 1
8#         element at position 3 goes to position 4
9#         element at position 4 goes to position 3
10
11# Inverse Q: position j maps back to position Q[j]
12# Q undoes P: if P[i] = j, then Q[j] = i
13Q = np.array([1, 2, 0, 4, 3])
14
15# Verify: applying P then Q returns the identity
16data = np.array([10, 20, 30, 40, 50])
17shuffled = data[P]        # [30, 10, 20, 50, 40]
18restored = shuffled[Q]    # [10, 20, 30, 40, 50] — original order

Method 1: np.argsort (Simplest)

python
1import numpy as np
2
3P = np.array([2, 0, 1, 4, 3])
4
5# argsort returns indices that would sort P
6Q = np.argsort(P)
7print(Q)  # [1, 2, 0, 4, 3]
8
9# Why this works:
10# P = [2, 0, 1, 4, 3]
11# Sorted P would be [0, 1, 2, 3, 4]
12# To sort P, take elements at indices [1, 2, 0, 4, 3]
13# These indices are exactly the inverse permutation

np.argsort has O(n log n) complexity due to sorting. For permutation arrays (which contain each index exactly once), this gives the correct inverse.

Method 2: Direct Index Assignment (Fastest)

python
1import numpy as np
2
3P = np.array([2, 0, 1, 4, 3])
4
5# Create the inverse by direct assignment
6Q = np.empty_like(P)
7Q[P] = np.arange(len(P))
8print(Q)  # [1, 2, 0, 4, 3]
9
10# This works because:
11# Q[P[0]] = 0 → Q[2] = 0
12# Q[P[1]] = 1 → Q[0] = 1
13# Q[P[2]] = 2 → Q[1] = 2
14# Q[P[3]] = 3 → Q[4] = 3
15# Q[P[4]] = 4 → Q[3] = 4

This method is O(n) and avoids the overhead of sorting. It is the fastest approach for large arrays.

Performance Comparison

python
1import numpy as np
2import timeit
3
4n = 1_000_000
5P = np.random.permutation(n)
6
7# Method 1: argsort
8t1 = timeit.timeit(lambda: np.argsort(P), number=100)
9
10# Method 2: direct assignment
11def direct_inverse(P):
12    Q = np.empty_like(P)
13    Q[P] = np.arange(len(P))
14    return Q
15
16t2 = timeit.timeit(lambda: direct_inverse(P), number=100)
17
18print(f"argsort:          {t1:.3f}s")
19print(f"direct assignment: {t2:.3f}s")
20# direct assignment is typically 2-3x faster for large arrays

Verifying the Inverse

python
1import numpy as np
2
3P = np.array([3, 1, 4, 0, 2])
4Q = np.argsort(P)
5
6# Property 1: P[Q] = identity
7print(P[Q])  # [0, 1, 2, 3, 4]
8
9# Property 2: Q[P] = identity
10print(Q[P])  # [0, 1, 2, 3, 4]
11
12# Both P[Q] and Q[P] should equal np.arange(len(P))
13assert np.array_equal(P[Q], np.arange(len(P)))
14assert np.array_equal(Q[P], np.arange(len(P)))

An inverse permutation satisfies both P[Q] = identity and Q[P] = identity.

Practical Use Case: Undoing a Shuffle

python
1import numpy as np
2
3# Shuffle data and record the permutation
4data = np.array(["apple", "banana", "cherry", "date", "elderberry"])
5P = np.random.permutation(len(data))
6shuffled = data[P]
7
8print(f"Original:  {data}")
9print(f"Shuffled:  {shuffled}")
10
11# Later, recover the original order
12Q = np.argsort(P)
13restored = shuffled[Q]
14print(f"Restored:  {restored}")
15
16assert np.array_equal(data, restored)

Inverting a Permutation Matrix

python
1import numpy as np
2
3# A permutation matrix is a square matrix with exactly one 1 per row and column
4P = np.array([2, 0, 1])
5n = len(P)
6
7# Build permutation matrix
8perm_matrix = np.zeros((n, n), dtype=int)
9perm_matrix[np.arange(n), P] = 1
10print(perm_matrix)
11# [[0, 0, 1],
12#  [1, 0, 0],
13#  [0, 1, 0]]
14
15# Inverse of a permutation matrix is its transpose
16inv_matrix = perm_matrix.T
17print(inv_matrix)
18# [[0, 1, 0],
19#  [0, 0, 1],
20#  [1, 0, 0]]
21
22# Extract inverse permutation from the matrix
23Q = np.argmax(inv_matrix, axis=1)
24print(Q)  # [1, 2, 0]

Self-Inverse (Involution) Permutations

python
1import numpy as np
2
3# Some permutations are their own inverse
4P = np.array([1, 0, 3, 2, 4])  # swaps (0,1) and (2,3), fixes 4
5Q = np.argsort(P)
6print(Q)                         # [1, 0, 3, 2, 4] — same as P!
7print(np.array_equal(P, Q))      # True — P is an involution
8
9# All transposition-only permutations are involutions
10swap = np.arange(10)
11swap[[3, 7]] = swap[[7, 3]]  # swap positions 3 and 7
12print(np.array_equal(swap, np.argsort(swap)))  # True

Common Pitfalls

  • Using np.argsort on non-permutation arrays: np.argsort always returns valid indices, but the result is only a true permutation inverse when the input is a valid permutation (contains each integer from 0 to n-1 exactly once). For arrays with duplicates, the result is not an inverse.
  • Forgetting that NumPy uses 0-based indexing: If your permutation is 1-based (e.g., [3, 1, 2] meaning positions 1-3), subtract 1 before inverting and add 1 after: Q = np.argsort(P - 1) + 1.
  • Modifying the array in-place during inversion: P[P] = np.arange(len(P)) does not work because the left side and right side both depend on P. Use a separate output array: Q = np.empty_like(P); Q[P] = np.arange(len(P)).
  • Assuming argsort is always the fastest: For small arrays (< 1000 elements), argsort and direct assignment have similar performance. For millions of elements, the O(n) direct assignment method is significantly faster than O(n log n) argsort.
  • Not verifying the result: A common validation is to check that P[Q] equals np.arange(len(P)). Skipping this check can hide bugs when the input is not a valid permutation.

Summary

  • Use np.argsort(P) for the simplest one-liner permutation inverse
  • Use Q[P] = np.arange(len(P)) for the fastest O(n) inverse computation
  • Verify the inverse with assert np.array_equal(P[Q], np.arange(len(P)))
  • Both P[Q] and Q[P] must equal the identity array for a valid inverse
  • For 1-based permutations, convert to 0-based before inverting
  • The direct assignment method is 2-3x faster than argsort for large arrays
Related reading
Course
Intermediate
27 lessons
15 hours
DSA Fundamentals

Master algorithmic patterns and data structures through hands-on LeetCode-style problems - from arrays and hashing to dynamic programming and advanced graphs.

View the course
Track what you have practised

A free account saves your progress, solutions and study plan across every problem on Codemia.

ML System Design practice on Codemia

Design recommenders, ranking systems and training pipelines the way ML interviews actually ask for them, with worked solutions.

Practice ML system design
Codemia
© 2026 Codemia
Resources
Legal
Social
All Rights Reserved.