0-dan n - 1-ə qədər sıralama#8636

0-dan n - 1-ə qədər sıralama (Həll təhlili)

Verilmiş ardıcıllığı $0$ -dan $n - 1$ n - 1-ə qədər ədədlərin bir permutasiyası kimi nəzərdən keçirək. Onu müstəqil dövrlərə (cycle) parçalanma şəklində təqdim edək.

Hər bir dövrü digərlərindən asılı olmayaraq sıralamaq olar. Tutaq ki, dövrün uzunluğu $k$ -dir. Onda bu dövrün bütün elementlərini öz düzgün yerlərinə qoymaq üçün $k - 1$ k - 1 mübadilə kifayətdir. Doğrudan da, dövrdə məhz bir elementi dərhal düzgün mövqeyinə qoymaq olar, bundan sonra uzunluğu $k - 1$ k - 1 olan dövr qalır və proses eyni qaydada davam edir.

$0$ -dan $n - 1$ n - 1-ə qədər bütün $i$ indekslərini nəzərdən keçirək. Əgər $a_{i} = i$ a_i = i-dirsə, deməli element artıq öz yerindədir və heç nə etmək lazım deyil. Əgər $a_{i} \neq = i$ a_i \ne i-dirsə, bu o deməkdir ki, biz hələ emal olunmamış bir dövr tapmışıq.

Sonra bu dövrü “açmağa” başlayırıq. $a_{i} \neq = i$ a_i \ne i olduğu müddətdə $i$ və $a_{i}$ a_i mövqelərindəki elementləri yer dəyişirik. Belə mübadilədən sonra $a_{i}$ a_i elementi öz düzgün yerinə düşür. Bu əməliyyatı təkrar edərək cari dövrün bütün elementlərini yerinə yerləşdiririk.

Beləliklə, minimal mübadilə sayını tapmaq üçün kifayətdir:

Permutasiyanı dövrlərə parçalamaq;
Uzunluğu $k$ olan hər bir dövr üçün cavaba $k - 1$ k - 1 əlavə etmək.

Nümunə

İkinci nümunəni nəzərdən keçirək. $(4, 0, 3, 2, 1)$ (4, 0, 3, 2, 1) permutasiyası iki dövrə parçalanır:

$(4, 1, 0)$ (4, 1, 0) uzunluğu $3$ ;
$(3, 2)$ uzunluğu $2$ ;

Birinci dövr üçün $3 - 1 = 2$ 3 - 1 = 2 mübadilə, ikinci üçün isə $2 - 1 = 1$ 2 - 1 = 1 mübadilə lazımdır. Beləliklə, ümumi minimal mübadilə sayı $2 + 1 = 3$ 2 + 1 = 3-ə bərabərdir.

Alqoritmin reallaşdırılması

Giriş permutasiyasını $a$ massivində saxlayacağıq. Yerinə yetirilmiş mübadilələri $an s$ massivində saxlayırıq.

vector<int> a;
vector<pair<int, int> > ans;

Giriş permutasiyasını oxuyuruq.

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

Əgər $a_{i} \neq = i$ a_i \ne i-dirsə, onda $a_{i}$ a_i elementinin aid olduğu dövrü emal edirik və lazımi mübadilələri yerinə yetiririk. Yerinə yetirilmiş mübadilələrin sayını $c n t$ dəyişənində sayırıq.

for (i = 0; i < n; i++)
  while (a[i] != i)
  {
    ans.push_back(make_pair(i, a[i]));
    swap(a[i], a[a[i]]);
    cnt++;
  }

C++

Mübadilələrin sayını $c n t$ , sonra isə mübadilələrin özünü çıxışa veririk.

printf("%d\n", cnt);
for (i = 0; i < ans.size(); i++)
  printf("%d %d\n", ans[i].first, ans[i].second);