İxtiyari qarışdırma#1584

İxtiyari qarışdırma (Həll təhlili)

Əvvəlcə bizdə ${1, 2, ..., n}$ \{1, 2, ..., n\} massivi var. Sonra qarışdırma (tasovka) prosedurası yerinə yetirilir. Bizə son yerdəyişmə (permutasiya) $A$ verilib. Prosedur yerinə yetirildikdən sonra məhz onu əldə etmək ehtimalını tapmaq lazımdır.

Axtarılan ehtimal bərabərdir:

\frac{А - n ı ə l d ə e t m ə nin u ¨ s u l l a r ı n ı n s a y ı}{q a r ı s \c d ı r man ı n u ¨ m u mi u ¨ s u l l a r ı n ı n s a y ı}

\frac{А-nı~əldə~etmənin~üsullarının~sayı}{qarışdırmanın~ümumi~üsullarının~sayı}

Qarışdırmanın hər addımında bir $r$ ədədi seçilir. $r$ ədədinin seçilmə variantlarının sayı $n$ -ə bərabərdir. Qarışdırma addımlarının sayı da $n$ -dir. Deməli, $n^{n}$ n^n seçim ardıcıllığı mövcuddur. Qeyd edək ki, müxtəlif seçim ardıcıllıqları eyni yekun yerdəyişməyə gətirib çıxara bilər. Çünki $n^{n}$ n^n sayı $n!$ -dan xeyli böyükdür.

$c u r$ massivinə ${1, 2, ..., n}$ \{1, 2, ..., n\} ardıcıllığını yazaq. $c u r$ -da bütün mümkün qarışdırma proseslərini $(1 \leq r_{i} \leq n)$ (1 \le r_i \le n) modelləşdirərək, bütün mümkün seçim variantlarını $(r_{1}, r_{2}, ..., r_{n})$ (r_1, r_2, ..., r_n) perebor edəcəyik. Qeyd edək ki, $r_{1}, r_{2}, ..., r_{n}$ r_1, r_2, ..., r_n ədədlərinin sabitlənmiş ardıcıllığı hər addımda məhz hansı mübadilələrin yerinə yetiriləcəyini, deməli, prosedur bitdikdən sonrakı yekun massivi də birmənalı olaraq müəyyən edir. Əgər bütün mübadilələr tətbiq edildikdən sonra $A$ massivini əldə etmişiksə, cəhdi uğurlu hesab edirik. Tutaq ki, belə cəhdlər $s$ ədəd alındı. Onda axtarılan ehtimal bərabərdir:

s / n^{n}

s / n^n

Qarışdırma prosesinin bütün mümkün davamlarını rekursiv şəkildə perebor edən və onlardan neçəsinin hədəf $A$ yerdəyişməsinə gətirdiyini hesablayan shuffle funksiyasını reallaşdıraq.

Funksiyanın bir parametri var: $p os$ — cari iterasiyanın nömrəsi ( $0$ -dan başlayır). Bu o deməkdir ki, ilk $p os$ mübadilə artıq yerinə yetirilib, $c u r$ massivi isə bu əməliyyatlardan sonra alınan vəziyyəti saxlayır.

Vaxt məhdudiyyətinə uyğunlaşmaq üçün aşağıdakı kəsmədən (отсечение) istifadə edəcəyik. Tutaq ki, $p os$ nömrəli iterasiya yerinə yetirilir və cari $c u r$ massivi hədəf $A$ massivindən $d i f f$ pozisiyada fərqlənir. Hələ $n - p os$ n - pos mübadilə yerinə yetirilməlidir. Qeyd edək ki, bir mübadilə ilə ən çoxu iki elementi öz yerinə qoymaq olar. Deməli, qalan addımlar ərzində cəmi maksimum $2 \cdot (n - p os)$ 2 \cdot (n - pos) pozisiyanı düzəltmək mümkündür.

Əgər $d i f f \textgreater 2 \cdot (n - p os)$ diff \textgreater 2 \cdot (n - pos) olarsa, onda $c u r$ -dan $A$ massivini artıq əldə etmək mümkün deyil. Bu halda sonrakı perebora ehtiyac yoxdur və rekursiyanın cari budağını dərhal dayandırmaq olar.

Alqoritmin realizasiyası

İşçi massivləri elan edək:

$a$ — verilmiş $А$ yerdəyişməsi;
$c u r$ — perebor zamanı cari yerdəyişmə;

int a[10], cur[10];

shuffle funksiyası qarışdırma prosesinin bütün mümkün davamlarını rekursiv şəkildə perebor edərək, onlardan neçəsinin hədəf $A$ yerdəyişməsinə gətirəcəyini hesablayır.

void shuffle(int pos) 
{

Bütün $n$ əməliyyat yerinə yetirilib. Yalnız yoxlamaq qalır — əldə edilmiş $c u r$ massivi tələb olunan $A$ ilə üst-üstə düşürmü. Əgər düşürsə, deməli, daha bir uğurlu ssenari tapılıb. Bu halda $co u n tG oo d$ -u artırırıq.

  if (pos == n) 
  {
    for (int i = 0; i \textless n; i++)
      if (cur[i] != a[i]) return;
    countGood++;
    return;
  }

C++

$d i f f$ dəyişənində cari $c u r$ massivinin tələb olunan $A$ -dan neçə pozisiyada fərqləndiyini hesablayırıq.

  int diff = 0;
  for (int i = 0; i \textless n; i++)
    if (cur[i] != a[i]) diff++;

Hazırda bizə $n - p os$ n - pos addım yerinə yetirmək qalır. Bir mübadilə ilə maksimum iki yanlış pozisiyanı düzəltmək olar. Əgər artıq hazırda fərqlərin sayı bundan çoxdursa, rekursiyanı davam etdirməyin mənası yoxdur.

Sadəcə peреborun bu budağına baxmağı dayandırırıq.

  if (diff \textgreater 2 * (n - pos)) return;

$r$ -in bütün mümkün qiymətlərini perebor edirik.

  for (int r = 0; r \textless n; r++) 
  {
    swap(cur[pos], cur[r]);
    shuffle(pos + 1);
    swap(cur[pos], cur[r]);
  }
}

C++

Proqramın əsas hissəsi. $n$ ədədini — $А$ massivinin ölçüsünü oxuyuruq.

while (scanf("%d", \&n) == 1)
{

Giriş $А$ massivini oxuyuruq. Modelləşdirmə həmişə ${1, 2, ..., n}$ \{1, 2, ..., n\} massivindən başlayır. Onu da $c u r$ -a yazırıq.

  for (int i = 0; i \textless n; i++)
  {
    scanf("%d", \&a[i]);
    cur[i] = i + 1;
  }

Pereboru işə salırıq. $co u n tG oo d$ dəyişənində hansı say təsadüfi seçim ardıcıllıqlarının $A$ massivinə gətirdiyini hesablayırıq.

  countGood = 0;
  shuffle(0);

Cavabı hesablayıb çap edirik.

  res = countGood / pow(n, n);
  printf("%.6lf\n", res);
}