h2. "PermutariAB":https://www.infoarena.ro/problema/permutariab

Un lucru foarte interesant la această problemă este faptul că o putem reduce la a sorta crescător o permutare. Mai exact, vom transforma permutarea B într-o permutare Bt, astfel încât aplicând aceleaşi operaţii de swap, în aceeaşi ordine, necesare sortării în ordine crescătoare a permutării Bt pe permutarea B, să obţinem permutarea A. Acum rămâne de văzut cum construim permutarea Bt. Să ne uităm la permutarea A, să luam un indice 1 <= i <= N şi să constatăm că pe poziţia i se află o valoare x (i.e. A[i] = x). Deci, după aplicarea operaţiilor de swap aferente transformării lui B în A, valoarea x trebuie să se afle pe poziţia i. Astfel, în Bt, pe poziţia j care are B[j] = x, în Bt vom pune valoarea i (i.e. Bt[j] = i), astfel spunându-ţi "Bă, eu vreau ca valoarea de pe poziţia j să ajungă pe poziţia i după efectuarea swap-urilor". Iar lucrul care face asta este ordonarea crescătoare a permutării Bt. În continuare, voi face afirmaţia că numărul minim de swap-uri necesar sortării permutării Bt este egal cu numărul de inversiuni ale permutării Bt, afirmaţie pe care am să o demonstrez în cele ce urmează. Readuc aminte faptul că o inversiune este o pereche de indici (i, j) cu i < j şi A[i] > A[j]. De aici rezultă ca numărul de inversiuni ale unei permutări sortate (permutarea identică) are 0 inversiuni şi este unica permutare cu 0 inversiuni. Să analizăm ce efecte are o operaţie de swap:

Un lucru foarte interesant la această problemă este faptul că o putem reduce la a sorta crescător o permutare. Mai exact, vom transforma permutarea B într-o permutare Bt astfel încât aplicând aceleaşi operaţii de swap, în aceeaşi ordine, necesare sortării în ordine crescătoare a permutării Bt pe permutarea B, să obţinem permutarea A. Acum rămâne de văzut cum construim permutarea Bt. Să ne uităm la permutarea A, să luam un indice 1 <= i <= N şi să constatăm că pe poziţia i se află o valoare x (i.e. A[i] = x). Deci, după aplicarea operaţiilor de swap aferente transformării lui B în A, valoarea x trebuie să se afle pe poziţia i. Astfel, în Bt, pe poziţia j care are B[j] = x, în Bt vom pune valoarea i (i.e. Bt[j] = i), astfel spunându-ţi "Bă, eu vreau ca valoarea de pe poziţia j să ajungă pe poziţia i după efectuarea swap-urilor". Iar lucrul care face asta este ordonarea crescătoare a permutării Bt. În continuare, voi face afirmaţia că numărul minim de swap-uri necesar sortării permutării Bt este egal cu numărul de inversiuni ale permutării Bt, afirmaţie pe care am să o demonstrez în cele ce urmează. Readuc aminte faptul că o inversiune este o pereche de indici (i, j) cu i < j şi A[i] > A[j]. De aici rezultă ca numărul de inversiuni ale unei permutări sortate (permutarea identică) are 0 inversiuni şi este unica permutare cu 0 inversiuni. Să analizăm ce efecte are o operaţie de swap:

1) Dacă Bt[i] < Bt[i + 1] şi facem swap între ele, numărul de inversiuni va creşte cu 1.
2) Dacă Bt[i] > Bt[i + 1] şi facem swap între ele, numărul de inversiuni va scădea cu 1.