Permutasiya ardıcıllığının dərəcəsi#1789

Permutasiya ardıcıllığının dərəcəsi (Həll təhlili)

Qoy $p$ verilmiş çevirmə olsun və $p [i]$ çevirmənin $i$ mövqeyində olan elementi olsun. Elementlər ardıcıllığını nəzərə alaq: $i, p [i], p [p [i]], ...$ i, p[i], p[p[i]], ... Belə ki, çevirmədə elementlərin sayı məhduddur, belə minimal $k$ mövcuddur ki, $p [i]^{k} = i$ p[i]^k = i. Elementlər ardıcıllığını $i, p [i], p [p [i]], ..., p [i]^{k - 1}$ i, p[i], p[p[i]], ..., p[i]^{k-1}, burada $p [i]^{k} = i$ p[i]^k = i, biz dövr adlandıracağıq. Dövrün uzunluğu $k$ -ya bərabərdir.

Hər hansı bir çevirməni dövrlər siyahısı şəklində təqdim etmək olar. Məsələn, çevirmə $[4, 3, 2, 5, 1, 6]$ [4, 3, 2, 5, 1, 6] $(1, 4, 5) (2, 3) (6)$ (1, 4, 5)(2, 3)(6) şəklində təqdim olunur.

Məsələn, ardıcıl elementlər $(1, p [1], p [p [1]]) = (1, 4, 5)$ (1, p[1], p[p[1]]) = (1, 4, 5) dövr yaradır, çünki $p [p [p [1]]] = p [1]^{3} = 1$ p[p[p[1]]] = p[1]^3 = 1. Bu dövrün uzunluğu $3$ -ə bərabərdir.

Çevirmənin dərəcəsi dövrlərinin uzunluqlarının ƏKOB-una bərabərdir.

Misal

Birinci misalda çevirmə $[4, 3, 2, 5, 1, 6]$ [4, 3, 2, 5, 1, 6] $(1, 4, 5) (2, 3) (6)$ (1, 4, 5)(2, 3)(6) şəklində təqdim olunur. Dövrlərin uzunluqları $3, 2$ və $1$ -dir. Çevirmənin dərəcəsi $Ə K O B (3, 2, 1) = 6$ ƏKOB(3, 2, 1) = 6-ya bərabərdir.

İkinci misalda çevirmə $[4, 3, 6, 8, 9, 7, 2, 1, 5]$ [4, 3, 6, 8, 9, 7, 2, 1, 5] $(1, 4, 8) (2, 3, 6, 7) (5, 9)$ (1, 4, 8)(2, 3, 6, 7)(5, 9) şəklində təqdim olunur. Dövrlərin uzunluqları $3, 4$ və $2$ -dir. Çevirmənin dərəcəsi $Ə K O B (3, 4, 2) = 12$ ƏKOB(3, 4, 2) = 12-yə bərabərdir.

Alqoritmin reallaşdırılması

$p$ massiv daxil olan çevirməni saxlayır. $u se d$ massiv işlənmiş elementləri işarələmək üçün istifadə olunur.

#define MAX 101
int p[MAX], used[MAX];

Daxil olan çevirməni oxuyuruq.

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

$r es$ dəyişənində çevirmənin $p$ dərəcəsini hesablamaq.

res = 1;
memset(used, 0, sizeof(used));

Çevirmənin indekslərini yoxlayırıq. Hər bir işlənmiş index üçün $i$ , $u se d [i] = 1$ used[i] = 1 qoyulur.

for (i = 1; i <= n; i++)
  if (!used[i])
  {

$p [i]$ elementi ilə dövr hələ aşkar olunmayıb. Dövrün uzunluğunu $l e n$ indeksindən başlayaraq tapırıq $j = i$ j = i. Bunun üçün ardıcıl olaraq $j, p [j], p [p [j]], ...$ j, p[j], p[p[j]], ... indekslərinə keçirik, artıq keçilmiş elementi qarşılaşana qədər. Bütün keçilən indeksləri $j$ , $u se d [j] = 1$ used[j] = 1 qoyaraq işarələyirik.

    len = 0;
    j = i;
    while (!used[j])
    {
      used[j] = 1;
      j = p[j];
      len++;
    }

C++

Dəyişən $l e n$ tapılmış cari dövrün uzunluğunu saxlayır. Bütün dövrlərin uzunluqlarının ƏKOB-unu hesablayırıq.

    res = lcm(res, len);
  }

Cavabı çıxarırıq.

printf("%d\n", res);