Permutazione inversa#1788

Permutazione inversa (Editoriale)

Una permutazione di ordine $n$ è una sequenza $p = (p [1], p [2], \dots, p [n])$ p = (p[1], p[2], \ldots, p[n]) in cui ogni numero da $1$ a $n$ compare esattamente una volta. È conveniente considerare una permutazione come un'applicazione che porta il numero $i$ nel numero $p [i]$ : $i \to p [i]$ i \to p[i].

La inversa di una permutazione $p$ è la permutazione $p^{- 1}$ p^{-1} che riporta ogni numero al proprio posto: se $p$ porta $i$ in $p [i]$ , allora $p^{- 1}$ p^{-1} riporta $p [i]$ in $i$ . In altre parole, per tutti gli $i$ vale la seguente uguaglianza:

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

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

Questa uguaglianza fornisce direttamente l'algoritmo: il numero $i$ deve trovarsi nella posizione $p [i]$ della permutazione inversa. Si itera su tutti gli $i$ da $1$ a $n$ e si esegue per ciascuno l'assegnazione $p i [p [i]] = i$ pi[p[i]] = i, dove l'array $p i$ memorizza la permutazione inversa.

Ogni posizione dell'array $p i$ viene riempita esattamente una volta. Infatti, i valori $p [1], p [2], \dots, p [n]$ p[1], p[2], \ldots, p[n] sono a due a due distinti e coprono tutti i numeri da $1$ a $n$ , quindi anche gli indici $p [i]$ sono a due a due distinti e coprono tutte le posizioni da $1$ a $n$ .

Notazione a due righe. Una permutazione viene spesso scritta su due righe: la riga superiore contiene i numeri $1, 2, \dots, n$ 1, 2, \ldots, n, e sotto ogni numero $i$ compare il valore $p [i]$ . Per ottenere la permutazione inversa, basta scambiare le righe e ordinare le colonne in ordine crescente rispetto alla riga superiore.

Esempio

Consideriamo la permutazione dell'esempio. Scriviamola insieme alla sua inversa nella notazione a due righe:

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}

Troviamo $p^{- 1}$ p^{-1} usando la 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

Otteniamo $p^{- 1} = (3, 1, 2)$ p^{-1} = (3, 1, 2). La notazione a due righe fornisce lo stesso risultato: scambiando le righe della permutazione $p$ , otteniamo le colonne $(2; 1)$ , $(3; 2)$ , $(1; 3)$ . Ordinandole secondo la riga superiore, otteniamo la riga inferiore $3, 1, 2$ .

Nella figura, la permutazione è rappresentata come frecce $i \to p [i]$ i \to p[i]. Nella permutazione inversa, tutte le frecce puntano nella direzione opposta: $p [i] \to i$ p[i] \to i.

Implementazione dell'algoritmo

L'array $p$ memorizza la permutazione in input, e l'array $p i$ memorizza la permutazione inversa.

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

Leggiamo la permutazione in input.

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

Calcoliamo la permutazione inversa.

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

Stampiamo la permutazione inversa.

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

Implementazione in Python

La lista $p$ memorizza la permutazione in input, e la lista $p i$ memorizza la permutazione inversa. Leggiamo i dati in input.

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

Calcoliamo la permutazione inversa.

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

Stampiamo la permutazione inversa.

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