Inverse permutation#1788

Inverse permutation (Editorial)

A permutation of order $n$ is a sequence $p = (p [1], p [2], \dots, p [n])$ p = (p[1], p[2], \ldots, p[n]) in which each number from $1$ to $n$ occurs exactly once. It is convenient to view a permutation as a mapping that takes the number $i$ to the number $p [i]$ : $i \to p [i]$ i \to p[i].

The inverse of a permutation $p$ is the permutation $p^{- 1}$ p^{-1} that returns every number to its place: if $p$ takes $i$ to $p [i]$ , then $p^{- 1}$ p^{-1} takes $p [i]$ back to $i$ . In other words, for all $i$ the following equality holds:

p^{- 1} [p [i]] = i

p^{-1}[p[i]] = i

This equality directly gives the algorithm: the number $i$ must be at position $p [i]$ of the inverse permutation. Iterate over all $i$ from $1$ to $n$ and perform the assignment $p i [p [i]] = i$ pi[p[i]] = i for each of them, where the array $p i$ stores the inverse permutation.

Each position of the array $p i$ is filled exactly once. Indeed, the values $p [1], p [2], \dots, p [n]$ p[1], p[2], \ldots, p[n] are pairwise distinct and cover all numbers from $1$ to $n$ , so the indices $p [i]$ are also pairwise distinct and cover all positions from $1$ to $n$ .

Two-line notation. A permutation is often written in two lines: the top line contains the numbers $1, 2, \dots, n$ 1, 2, \ldots, n, and under each number $i$ stands the value $p [i]$ . To obtain the inverse permutation, it is enough to swap the lines and sort the columns in increasing order of the top line.

Example

Consider the permutation from the example. Let us write it and its inverse in two-line notation:

p = (122331), p^{- 1} = (132132)

p = \begin{pmatrix} 1 & 2 & 3 \\ 2 & 3 & 1 \end{pmatrix}, \qquad p^{-1} = \begin{pmatrix} 1 & 2 & 3 \\ 3 & 1 & 2 \end{pmatrix}

Let us find $p^{- 1}$ p^{-1} using the formula $p i [p [i]] = i$ pi[p[i]] = i:

p i [p [1]] = p i [2] = 1, p i [p [2]] = p i [3] = 2, p i [p [3]] = p i [1] = 3

pi[p[1]] = pi[2] = 1, \quad pi[p[2]] = pi[3] = 2, \quad pi[p[3]] = pi[1] = 3

We get $p^{- 1} = (3, 1, 2)$ p^{-1} = (3, 1, 2). Two-line notation gives the same result: swapping the lines of the permutation $p$ , we obtain the columns $(2; 1)$ , $(3; 2)$ , $(1; 3)$ . Sorting them by the top line, we get the bottom line $3, 1, 2$ .

In the figure, the permutation is shown as arrows $i \to p [i]$ i \to p[i]. In the inverse permutation, all arrows point in the opposite direction: $p [i] \to i$ p[i] \to i.

Algorithm implementation

The array $p$ stores the input permutation, and the array $p i$ stores the inverse permutation.

#define MAX 20010
int p[MAX], pi[MAX];

Read the input permutation.

scanf("%d",&n);
for(i = 1; i <= n; i++)
  scanf("%d",&p[i]);

Compute the inverse permutation.

for(i = 1; i <= n; i++)
  pi[p[i]] = i;

Print the inverse permutation.

for(i = 1; i <= n; i++)
  printf("%d ",pi[i]);
printf("\n");

Python implementation

The list $p$ stores the input permutation, and the list $p i$ stores the inverse permutation. Read the input data.

n = int(input())
p = [0] + list(map(int, input().split()))
pi = [0] * (n + 1)

Compute the inverse permutation.

for i in range(1, n + 1):
  pi[p[i]] = i

Print the inverse permutation.

for i in range(1, n + 1):
  print(pi[i], end=" ")
print()