Обернена перестановка#1788

Обернена перестановка (Розбір)

Перестановкою порядку $n$ називається послідовність $p = (p [1], p [2], \dots, p [n])$ p = (p[1], p[2], \ldots, p[n]), в якій кожне число від $1$ до $n$ зустрічається рівно один раз. Зручно розглядати перестановку як відображення, що переводить число $i$ у число $p [i]$ : $i \to p [i]$ i \to p[i].

Оберненою до перестановки $p$ називається перестановка $p^{- 1}$ p^{-1}, яка повертає кожне число на своє місце: якщо $p$ переводить $i$ у $p [i]$ , то $p^{- 1}$ p^{-1} переводить $p [i]$ назад у $i$ . Іншими словами, для всіх $i$ виконується рівність:

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

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

Ця рівність одразу дає алгоритм: число $i$ має стояти на позиції $p [i]$ оберненої перестановки. Переберемо всі $i$ від $1$ до $n$ і для кожного з них виконаємо присвоєння $p i [p [i]] = i$ pi[p[i]] = i, де масив $p i$ зберігає обернену перестановку.

Кожна позиція масиву $p i$ заповнюється рівно один раз. Дійсно, значення $p [1], p [2], \dots, p [n]$ p[1], p[2], \ldots, p[n] попарно різні та охоплюють усі числа від $1$ до $n$ , тому індекси $p [i]$ також попарно різні та охоплюють усі позиції від $1$ до $n$ .

Дворядковий запис. Перестановку часто записують у два рядки: у верхньому рядку стоять числа $1, 2, \dots, n$ 1, 2, \ldots, n, а під кожним числом $i$ стоїть значення $p [i]$ . Щоб отримати обернену перестановку, достатньо поміняти рядки місцями та відсортувати стовпці за зростанням верхнього рядка.

Приклад

Розглянемо перестановку з прикладу. Запишемо її та обернену до неї перестановку у дворядковому вигляді:

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}

Знайдемо $p^{- 1}$ p^{-1} за формулою $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

Отримуємо $p^{- 1} = (3, 1, 2)$ p^{-1} = (3, 1, 2). Дворядковий запис дає той самий результат: поміняв рядки перестановки $p$ місцями, отримуємо стовпці $(2; 1)$ , $(3; 2)$ , $(1; 3)$ . Відсортувавши їх за верхнім рядком, отримуємо нижній рядок $3, 1, 2$ .

На малюнку перестановка зображена у вигляді стрілок $i \to p [i]$ i \to p[i]. В оберненій перестановці всі стрілки вказують у протилежному напрямку: $p [i] \to i$ p[i] \to i.

Реалізація алгоритму

Масив $p$ зберігає вхідну перестановку, а масив $p i$ зберігає обернену перестановку.

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

Зчитаємо вхідну перестановку.

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

Обчислимо обернену перестановку.

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

Виведемо обернену перестановку.

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

Реалізація мовою Python

Список $p$ зберігає вхідну перестановку, а список $p i$ зберігає обернену перестановку. Зчитаємо вхідні дані.

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

Обчислимо обернену перестановку.

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

Виведемо обернену перестановку.

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