Çörəklərin sıralanması#6828

Çörəklərin sıralanması (Həll təhlili)

Kürəklə edilən hiylə çörəklərin aşağıdakı yerdəyişməsini yerinə yetirir:

(a & b & c c & a & b)

\begin{pmatrix} a \& b \& c \\ c \& a \& b \end{pmatrix}

Onu qonşu elementlərin iki yerdəyişməsi şəklində təsvir etmək olar:

(a, b, c) \to (a, c, b) \to (c, a, b)

(a, b, c) → (a, c, b) → (c, a, b)

Qonşu elementlərin hər bir yerdəyişməsi permutasiyanın cütlüyünü dəyişir. Deməli, çörəklər üzərində göstərilən əməliyyat permutasiyanın cütlüyünü saxlayır.

Çörəyi Maykl-in rəisinin tələb etdiyi kimi sıralamaq yalnız o halda mümkündür ki, permutasiyaların cütlükləri üst-üstə düşsün.

Məsələnin xətti həlli onun üzərində qurulub ki, iki permutasiya eyni cütlüyə malikdir yalnız və yalnız onların ayrıldığı tsikllərin sayının cütlüyü üst-üstə düşdükdə.

Lemma. Permutasiyalar nəzəriyyəsinin aşağıdakı faktına baxaq:

p er m u t a s i y an ı n c u ¨ tl u ¨ y u ¨ = (n - t s ik l l ə r in s a y ı) m o d 2

permutasiyanın~cütlüyü = (n - tsikllərin~sayı)~mod~2

Buna görə də cütlüyü yoxlamaq üçün:

permutasiyanı tsikllərə ayırmaq;
onların sayını hesablamaq lazımdır.

Əgər iki permutasiyanın tsikl sayının cütlüyü eynidirsə, onların cütlükləri üst-üstə düşür.

Bu, intuitiv olaraq ondan irəli gəlir ki, $k$ uzunluğunda hər bir tsikli elementlərin $k - 1$ k - 1 dəyişməsindən yığmaq olar, ona görə də ümumi dəyişmələrin sayı bərabərdir

n - t s ik l l ə r in s a y ı

n - tsikllərin~sayı

Nümunə

Birinci nümunədə birinci permutasiya $2$ inversiya, ikincisi isə — $6$ inversiya ehtiva edir. Hər iki permutasiyadakı inversiyaların sayı eyni cütlüyə malikdir.

Permutasiyaları tsikllərə ayıraq:

$(1, 3, 4, 2) = (1) (3, 4, 2)$ (1, 3, 4, 2) = (1) (3, 4, 2);
$(4, 3, 2, 1) = (4, 1) (3, 2)$ (4, 3, 2, 1) = (4, 1) (3, 2);

Hər iki permutasiya iki tsikldən ibarətdir, yəni onlardakı tsikllərin sayı da eyni cütlüyə malikdir.

İkinci nümunədə birinci permutasiya $0$ inversiya, ikincisi isə — $15$ inversiya ehtiva edir. Bu permutasiyalardakı inversiyaların sayı fərqli cütlüyə malikdir.

Permutasiyaları tsikllərə ayıraq:

$(1, 2, 3, 4, 5, 6) = (1) (2) (3) (4) (5) (6)$ (1, 2, 3, 4, 5, 6) = (1) (2) (3) (4) (5) (6);
$(6, 5, 4, 3, 2, 1) = (6, 1) (5, 2) (4, 3)$ (6, 5, 4, 3, 2, 1) = (6, 1) (5, 2) (4, 3);

Birinci permutasiya $6$ tsikldən, ikincisi isə — $3$ tsikldən ibarətdir. Beləliklə, bu permutasiyalardakı tsikllərin sayının cütlüyü fərqlidir.

Alqoritmin realizasiyası

Permutasiyanı saxlamaq üçün massiv elan edək.

#define MAX 100010
int a[MAX];

run funksiyası $p os$ indeksindən başlayaraq permutasiyanın bir tsiklindən keçir. Hər addımda o, $p os \to a [p os]$ pos \to a[pos] qaydası ilə tsiklin növbəti elementinə keçir. Ziyarət edilmiş elementlər onları təkrar emal etməmək üçün $- 1$ qiyməti ilə işarələnir. Beləliklə, funksiya permutasiyanın bir tsiklini tam gəzir və onun bütün elementlərini artıq ziyarət edilmiş kimi qeyd edir.

void run(int pos)
{
  int v;
  while (a[pos] != -1)
  {
    v = a[pos];
    a[pos] = -1;
    pos = v;
  }
}

C++

parity funksiyası $a$ permutasiyasındakı tsikllərin sayının cütlüyünü hesablayır, yəni tsikllərin sayını $2$ -yə görə modul ilə qaytarır. Funksiya massivin bütün mövqelərini ardıcıl olaraq nəzərdən keçirir.

int parity(int *a)
{
  int res = 0;

Massivin bütün mövqelərini ardıcıl olaraq nəzərdən keçiririk.

  for (int i = 0; i < n; i++)

Əgər element hələ ziyarət edilməyibsə $(a [i] \neq = - 1)$ (a[i] \ne -1), bu, yeni tsiklin başlanğıcı deməkdir. Bu halda $r u n (i)$ funksiyası çağırılır, o, bütün tsikli gəzir və onun elementlərini $- 1$ qiyməti ilə işarələyir.

    if (a[i] != -1) 
    {
      run(i);

Tsikl gəzildikdən sonra $r es$ sayğacı $1$ artırılır.

      res++;
    }

Tsikllərin sayının cütlüyünü qaytarırıq.

  return res % 2;
}

Proqramın əsas hissəsi. Birinci permutasiyanı oxuyuruq. Oxuma zamanı elementlərin $1.. n$ nömrələnməsindən işləmək üçün daha rahat olan $0.. n - 1$ 0 .. n - 1 nömrələnməsinə keçmək üçün hər bir qiymət $1$ azaldılır $(a [i] - -)$ (a[i]--).

scanf("%d",&n);
for (i = 0; i < n; i++)
  scanf("%d",&a[i]), a[i]--;

$p 1$ dəyişənində $a$ permutasiyasındakı tsikllərin sayının cütlüyünü hesablayırıq.

p1 = parity(a);

İkinci permutasiyanı oxuyuruq. $p 2$ dəyişənində $a$ permutasiyasındakı tsikllərin sayının cütlüyünü hesablayırıq.

for (i = 0; i < n; i++)
  scanf("%d",&a[i]), a[i]--;
p2 = parity(a);

İki permutasiyadakı tsikllərin sayının cütlüklərini müqayisə edirik və cavabı çap edirik.

if (p1 == p2) printf("Possible\n");
else printf("Impossible\n");