Tərs dəyişdirmə#1788

Tərs dəyişdirmə (Həll təhlili)

$n$ dərəcəli permutasiya elə $p = (p [1], p [2], \dots, p [n])$ p = (p[1], p[2], \ldots, p[n]) ardıcıllığıdır ki, onda $1$ -dən $n$ -ə qədər hər bir ədəd dəqiq bir dəfə rast gəlir. Permutasiyaya $i$ ədədini $p [i]$ ədədinə göndərən inikas kimi baxmaq rahatdır: $i \to p [i]$ i \to p[i].

$p$ permutasiyasının tərsi elə $p^{- 1}$ p^{-1} permutasiyasıdır ki, o, hər bir ədədi öz yerinə qaytarır: əgər $p$ , $i$ -ni $p [i]$ -ə göndərirsə, onda $p^{- 1}$ p^{-1}, $p [i]$ -ni geriyə $i$ -yə göndərir. Başqa sözlə, bütün $i$ üçün aşağıdakı bərabərlik doğrudur:

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

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

Bu bərabərlik birbaşa alqoritmi verir: $i$ ədədi tərs permutasiyanın $p [i]$ mövqeyində olmalıdır. $i$ -ni $1$ -dən $n$ -ə qədər dəyişərək, hər biri üçün $p i [p [i]] = i$ pi[p[i]] = i mənimsətməsini yerinə yetirin, burada $p i$ massivi tərs permutasiyanı saxlayır.

$p i$ massivinin hər bir mövqeyi dəqiq bir dəfə doldurulur. Həqiqətən, $p [1], p [2], \dots, p [n]$ p[1], p[2], \ldots, p[n] qiymətləri cüt-cüt müxtəlifdir və $1$ -dən $n$ -ə qədər bütün ədədləri əhatə edir, deməli, $p [i]$ indeksləri də cüt-cüt müxtəlifdir və $1$ -dən $n$ -ə qədər bütün mövqeləri əhatə edir.

İki sətirli qeydiyyat. Permutasiya tez-tez iki sətirdə yazılır: üst sətirdə $1, 2, \dots, n$ 1, 2, \ldots, n ədədləri, hər bir $i$ ədədinin altında isə $p [i]$ qiyməti yerləşir. Tərs permutasiyanı əldə etmək üçün sətirləri yerdəyişmək və sütunları üst sətirin artma qaydasında sıralamaq kifayətdir.

Misal

Misaldan olan permutasiyaya baxaq. Onu və onun tərsini iki sətirli qeydiyyatda yazaq:

p = (1&2&3 2&3&1), p^{- 1} = (1&2&3 3&1&2)

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 i [p [i]] = i$ pi[p[i]] = i düsturundan istifadə edərək $p^{- 1}$ p^{-1}-i tapaq:

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) alırıq. İki sətirli qeydiyyat da eyni nəticəni verir: $p$ permutasiyasının sətirlərini yerdəyişdikdə, $(2; 1)$ , $(3; 2)$ , $(1; 3)$ sütunlarını alırıq. Onları üst sətirə görə sıraladıqda, alt sətir kimi $3, 1, 2$ alırıq.

Şəkildə permutasiya $i \to p [i]$ i \to p[i] oxları kimi göstərilmişdir. Tərs permutasiyada bütün oxlar əks istiqamətə yönəlir: $p [i] \to i$ p[i] \to i.

Alqoritmin reallaşdırılması

$p$ massivi daxiletmə permutasiyasını, $p i$ massivi isə tərs permutasiyanı saxlayır.

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

Daxiletmə permutasiyasını oxuyun.

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

Tərs permutasiyanı hesablayın.

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

Tərs permutasiyanı çap edin.

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

Python reallaşdırılması

$p$ siyahısı daxiletmə permutasiyasını, $p i$ siyahısı isə tərs permutasiyanı saxlayır. Daxiletmə məlumatlarını oxuyun.

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

Tərs permutasiyanı hesablayın.

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

Tərs permutasiyanı çap edin.

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