h2. 'Swap':problema/swap

Vom construi un o permutare $P$ a multimii ${1,...,N}$, asociata primului sir ({$N$} este lungimea fiecaruia din cele $2$ siruri). Pentru fiecare caracter $x$ din primul sir, vom calcula al catelea caracter de tipul respectiv este in cadrul primului sir (acest lucru se poate realiza usor in $O(N)$). Apoi vom construi permutarea $P$ in felul urmator: pentru fiecare caracter $x$, pentru care stim ca este al $y$-lea caracter de tipul sau si care se afla pe pozitia $i$, vom seta valoarea lui $P[i]$ ca fiind egala cu pozitia pe care se afla cel de-al $y$-lea caracter egal cu $x$ din cel de-al doilea sir. Numarul de operatii $swap$ necesare este egal cu numarul de inversiuni ale permutarii $P$. Acest numar poate fi determinat eficient in mai multe feluri: folosind mergesort (sortare prin interclasare), arbori de intervale, arbori indexati binar, impartirea in grupe de cate<tex>\sqrt N</tex> etc.

Vom construi o permutare $P$ a multimii ${1,...,N}$, asociata primului sir ({$N$} este lungimea fiecaruia din cele $2$ siruri). Pentru fiecare caracter $x$ din primul sir, vom calcula al catelea caracter de tipul respectiv este in cadrul primului sir (acest lucru se poate realiza usor in $O(N)$). Apoi vom construi permutarea $P$ in felul urmator: pentru fiecare caracter $x$, pentru care stim ca este al $y$-lea caracter de tipul sau si care se afla pe pozitia $i$, vom seta valoarea lui $P[i]$ ca fiind egala cu pozitia pe care se afla cel de-al $y$-lea caracter egal cu $x$ din cel de-al doilea sir. Numarul de operatii $swap$ necesare este egal cu numarul de inversiuni ale permutarii $P$. Acest numar poate fi determinat eficient in mai multe feluri: folosind mergesort (sortare prin interclasare), arbori de intervale, arbori indexati binar, impartirea in grupe de cate<tex>\sqrt N</tex> etc.

h2. 'Obj':problema/obj