2.1. Permutări
Fie . Să se scrie un program recursiv de generare a permutărilor de ordin n. De exemplu, pentru n = 3, programul va genera:
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
Soluţie: Permutările de ordin n reprezintă toate posibilităţile de a aranja elementele unei mulţimi de n elemente. Permutările de ordin n sunt funcţii bijective de forma:
a: {l, 2,..., n} –> {l, 2,..., n}. Reprezentăm o astfel de funcţie printr-un vector a cu n componente având semnificaţia: a[i] este elementul asociat prin intermediul funcţiei a elementului i ( ).
Condiţii:
– ;
– .
Observaţii:
1) În loc să verificăm pentru fiecare element i dacă este sau nu un potrivit pentru poziţia k prin compararea lui i cu elementele deja fixate în vectorul a (a [l], a [2],..., a[k - l]), am preferat să optimizăm funcţia de generare, utilizând o variabilă globală suplimentară (şirul aux). Acesta reprezintă şirul caracteristic al mulţimii elementelor imagine ale funcţiei a (aux [ i ] este l dacă elementul i a mai fost folosit, adică reprezintă deja imaginea unui element din mulţimea {l, 2, ..., k – l}, respectiv 0, dacă i nu a mai fost folosit). Când plasăm un număr i pe poziţia k, acesta reprezintă imaginea lui k prin intermediul funcţiei, deci aux [ i ] va deveni l. Când revenim dintr-un apel recursiv, pe poziţia k urmează să plasăm un alt număr, deci i nu va mai fi imaginea lui k, prin urmare aux [ i ] trebuie să redevină 0.
2) Numărul permutărilor de ordin n este: .
2.2. Aranjamente
Fie cu . Să se scrie un program recursiv care să genereze aranjamentele de n elemente luate câte m. De exemplu, pentru n = 3 şi m = 2, programul va genera:
1 2
1 3
2 1
2 3
3 1
3 2
Soluţie: Aranjamentele de n elemente luate câte m reprezintă toate submulţimile ordonate de m elemente ale unei mulţimi cu n elemente. Aranjamentele de n elemente luate câte m sunt funcţiile injective de forma: b: {l, 2,..., m} –> {l, 2,..., n}.
Reprezentăm o funcţie printr-un vector b, cu m componente, b [ i ] este elementul asociat prin intermediul funcţiei b elementului i ( ).
Condiţii:
– ;
– .
Singura diferenţă dintre generarea permutărilor şi generarea aranjamentelor constă în dimensiunea şirului soluţie.
Numărul aranjamente de n elemente luate câte m este::
Documentul este oferit gratuit,
trebuie doar să te autentifici in contul tău.