Pentru a rezolva problema initiala, propun sa rezolvam o versiune simplificata a ei. Sa presupunem ca orice interschimbare are costul 1. Care este costul minim ca sa sortam permutarea? Vom descompune permutarea in cicli. Oricare 2 cicli sunt disjuncti (un element apartine unui singur ciclu), deci costul sortarii permutarii este egal cu suma costurilor sortarii fiecarui ciclu.

Fie x1, x2, ..., xn elementele ciclului curent (adica perm(x1) = x2, perm(x2) = x3, ..., perm(xn-1) = xn, perm(xn) = x1). Costul sortarii acestui ciclu este n - 1. De ce? Sa presupunem ca intai vreau sa am grija ca elementul xn sa fie pe pozitia corecta. (perm(xn) = xn). Prin swap(x, y) inteleg ca voi interschimba valorile perm(x) si perm(y). Stiu ca perm(xn-1) = xn, deci daca fac swap(xn-1, xn), perm(xn) = xn si perm(xn-1) = x1. In continuare, vreau sa mai fac un swap astfel incat perm(xn-1) = xn-1. Stiu ca perm(xn-2) = xn-1. Daca fac swap(xn-2, xn-1), perm(xn-1) va fi xn-1 si perm(xn-2) = x1. Daca fac operatiile swap(xn, xn-1), swap(xn-1, xn-2), swap(xn-2, xn-3), .., swap(x3, x2), swap(x2, x1) voi sorta tot ciclul curent, folosind doar n - 1 operatii. Las ca tema pentru acasa demonstratia ca acest numar este minim pentru a sorta un ciclu. Mai jos am considerat un exemplu de sortare a unui ciclu dupa metoda descrisa.

Fie x1, x2, ..., xn elementele ciclului curent (adica perm(x1) = x2, perm(x2) = x3, ..., perm(xn - 1) = xn, perm(xn) = x1). Costul sortarii acestui ciclu este n - 1. De ce? Mai departe voi spune ca perm(x) = elementul care se afla pe pozitia x. Stiu ca pe pozitia x1 ar trebui sa fie elementul x1. Dar x1 se afla pe pozitia xn, deci schimb elementul de pe pozitia x1 cu elementul de pe pozitia xn (voi nota asta swap(x1, xn)). Pe pozitia xn se afla acum ce se afla inainte pe pozitia x1, adica x2. Pe pozitia x2 trebuie sa se afle elementul x2, deci fac swap(x2, xn). Acum pe pozitia xn se va afla elementul x3. Dupa ce fac operatiile swap(x1, xn), swap(x2, xn), swap(x3, xn), ..., swap(xn - 2, xn), swap(xn - 1, xn) permutarea va fi complet sortata. Practic, dupa i swap-uri, primele i elemente ale permutarii vor fi sortate. Dupa n - 1 swapuri, primele n - 1 elemente ale permutarii vor fi sortate, iar pe pozitia xn se va afla exact elementul xn, deci toata permutarea va fi sortata. In concluzie, pentru a sorta un ciclu de lungime n am nevoie de n - 1 operatii, iar pentru a sorta o permutare, costul va fi lungimea totala a ciclurilor - numarul de cicluri.

<tex>\begin{pmatrix}
1 & 2 &3  & 4 & 5\\
5 & 3 &4  & 1 & 2\
\end{pmatrix}
\rightarrow
\begin{pmatrix}
1 & 2 & 3 & 4 & 5\\
5 & 3 & 1 & 4 & 2
\end{pmatrix}
\rightarrow
\begin{pmatrix}
1 & 2 & 3 & 4 & 5\\
5 &  1 & 3 &4  & 2
\end{pmatrix}
\rightarrow
\begin{pmatrix}
1 & 2 &3  & 4 & 5\\
5 & 2 & 3 & 4 & 1
\end{pmatrix}
\rightarrow
\begin{pmatrix}
1 & 2 &3  & 4 &5 \\
1 & 2 & 3 & 4 & 5
\end{pmatrix}</tex>
Ce legatura are problema de mai sus cu problema noastra originala?

h2. 'Petrecere2':problema/petrecere2