\end{pmatrix}</tex>
In imagine avem x1 = 1, x2 = 5, x3 = 2, x4 = 3, x5 = 4.

 
Ce legatura are problema de mai sus cu problema noastra originala? Daca fac interschimbari numai cu elementul 1, problema se reduce la cea de sus. (costul unei operatii este min(1, x) = 1). Vom considera 4 cazuri diferite (care acopera defapt toata problema):
 
Caz 1. Lungimea ciclului curent este 1 (punct fix). In acest caz, ciclul este deja sortat, costul sortarii lui fiind 0.
Caz 2. Consideram un ciclu x1, x2, ..., xn, in care x1 = 1. Costul sortarii acestui ciclu este n - 1 (aceasta este exact problema de mai sus, deoarece la fiecare pas voi face interschimbari cu elementul 1).
Caz 3. (Caz particular, corespunzator testului 7) Avem un ciclu x1, x2, iar x1 = 2. Voi face pur si simplu swap(x1, x2), avand costul 2.
Caz 4. Avem un ciclu x1, x2, ..., xn si x1 este diferit de 1. Costul sortarii acestui ciclu este n + 1. Sa presupunem ca perm(1) = 1 (adica am rezolvat intai cazul 2). Fac intai swap(1, xn). Apoi fac algoritmul de la cazul 2. (in total n - 1 pasi). Apoi fac swap(1, x1). Astfel, sunt in total n + 1 operatii. Pentru a intelege mai bine, am mai luat un exemplu mai jos. De remarcat ca daca am aplica cazul acesta si pentru rezolvarea cazului 3, am obtine costul 3, care este incorect (cum am aratat mai sus, pot sorta cazul 3 numai cu costul 2). Pentru n >= 3, acest caz sorteaza optim, indiferent de permutare.
 
<tex>
\begin{pmatrix}
1 & 2 & 3 & 4 \\
1 & 4 & 2 & 3
\end{pmatrix}
\rightarrow
\begin{pmatrix}
1 &2  &3  &4 \\
2 &4  &1  &3
\end{pmatrix}
\rightarrow
\begin{pmatrix}
1 & 2 & 3 &4 \\
2 & 4 & 3 &1
\end{pmatrix}
\rightarrow
\begin{pmatrix}
1 & 2 & 3 &4 \\
2& 1 & 3 & 4
\end{pmatrix}
\rightarrow
\begin{pmatrix}
1 & 2 &3  &4 \\
 1& 2 &3  & 4
\end{pmatrix}
</tex>
 
Mai trebuie mentionat ca complexitatea algoritmului este data de complexitatea descompunerii in cicluri, care se face in O(N). Ca sursa de referinta voi folosi sursa mea din Arhiva Monthly: http://pastebin.com/uKm4TvN2

Ce legatura are problema de mai sus cu problema noastra originala?

h2. 'Petrecere2':problema/petrecere2