Metode de Programare - Elemente de Combinatorică

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::