tperm

TPerm

== include(page="template/taskheader" task_id="tperm") ==

Trei informaticieni romani au inventat un nou algoritm care genereaza toate cele $N!$ permutari cu $N$ elemente intr-o ordine specifica, pe care au numit-o *ordinea transpozitiilor*. Algoritmul porneste cu permutarea $1 2 3 .. N$. Apoi alege o pereche de $2$ elemente adiacente (localizate unul langa altul in permutare) si le interschimba. In felul acesta se obtine o permutare noua. Apoi se efectueaza acelasi procedeu pentru permutarea noua, obtinandu-se o alta permutare s.a.m.d. pana cand au fost generate (exact o data) toate cele $N!$ permutari. Va dati seama ca algoritmul trebuie sa fie destul de destept pentru a genera toate permutarile exact o data (fara repetitii).

Trei informaticieni romani au inventat un nou algoritm care genereaza toate cele $N!$ permutari cu $N$ elemente intr-o ordine specifica, pe care au numit-o *ordinea transpozitiilor*. Algoritmul porneste cu permutarea $1 2 3 .. N$. Apoi alege o pereche de $2$ elemente adiacente (localizate unul langa altul in permutare) si le interschimba. In felul acesta se obtine o permutare noua. Apoi se aplica aceeasi procedura asupra permutarii noi, obtinandu-se o alta permutare s.a.m.d. pana cand au fost generate (exact o data) toate cele $N!$ permutari. Va dati seama ca algoritmul trebuie sa fie destul de destept pentru a genera toate permutarile exact o data (fara repetitii).

Din fericire, dumneavoastra nu va trebui sa inventati un astfel de algoritm. De fapt, vi se dau fisierele 'perm.pas':problema/tperm?perm.pas si 'perm.cpp':problema/tperm?perm.cpp , care sunt $2$ implementari ale acestui algoritm, in Pascal si C/C++. El citesc numarul intreg $N$ de la intrarea standard si afiseaza in fisierul $perm.txt$ toate cele $N!$ permutari, cate una pe linie, in ordinea in care le genereaza algoritmul.

Din fericire, dumneavoastra nu va trebui sa inventati un astfel de algoritm. De fapt, vi se dau fisierele 'perm.pas':problema/tperm?perm.pas si 'perm.cpp':problema/tperm?perm.cpp , care sunt $2$ implementari ale acestui algoritm, in Pascal si C/C++. Ele citesc numarul intreg $N$ de la intrarea standard si afiseaza in fisierul $perm.txt$ toate cele $N!$ permutari, cate una pe linie, in ordinea in care le genereaza algoritmul.

Ceea ce trebuie sa faceti dumneavoastra este, data fiind o permutare, sa aflati pe ce pozitie se afla aceasta in sirul permutarilor generate de algoritm. Pozitiile sunt numerotate de la $1$ la $N!$.

Lansati in executie cele $2$ programe pentru $N=4$ si veti observa ca permutarea $2 3 1 4$ se va afla pe a $17$-a linie a fisierului $perm.txt$.
== include(page="template/taskfooter" task_id="tperm") ==

2300