Aceasta problema nu are demonstratie. Este un algoritm intuitiv pentru generarea tuturor permutarilor unei multimi de elemente date.
Pentru exemplificare am luat multimea elementelor {a,b,c}.
Descrierea algoritmului:
1. Se ia o permutare oarecare de start, fie ea (a,b,c)
2. Se construieste un tabel de ponderi, sau o matrice, cu dimensiunea 3X3 astfel:
1 2 3
a 0 0 0
b 0 0 0
c 0 0 0
3. Se noteaza permutarea de start in tabel, adica pe linia lui a, la prima coloana se adauga(insumeaza) cifra 1, la prima coloana deoarece a se afla pe prima pozitie in permutarea de start. La fel se procedeaza pentru fiecare element al permutarii, se aduna cifra 1 la linia si coloana corespunzatoare. Prin aceste insumari se obtine tabelul
1 2 3
a 1 0 0
b 0 1 0 (a,b,c)
c 0 0 1
4. Pentru generarea altei permutari se cauta prima cea mai mica valoare in matricea anteriorara. In cazul nostru prima cea mai mica valoare se afla (in ordine naturala) la pozitia a2. In tabelul urmator se va adauga cifra 1 la pozitia respectiva dar se tine cont de faptul ca la coloana 2 la anterioara permutare se afla elementul b. Astfel ca la actuala permutare elementul a va trece in locul lui b si invers, b in locul lui a. Celelalte elemente raman la locul lor, in cazul nostru mai este elementul c, care ramane la coloana 3. Deci, asa cum am spus, la pozitia a2 - care corespunde pozitiei lui a in permutarea actuala - vom aduna cifra 1. La fel vom aduna cifra 1 in tabel la pozitia corespunzatoare fiecarui element al noii permutari. Astfel generam urmatorul tabel, care tabel ne va ajuta, reluand aceiasi pasi, sa generam a treia permutare, si asa mai departe...
1 2 3
a 1 1 0
b 1 1 0 (b,a,c)
c 0 0 2
Iata mai jos matricele de ponderi ale permutarilor elementelor multimii {a,b,c}
a 1 0 0
b 0 1 0 (a,b,c)
c 0 0 1
a 1 1 0
b 1 1 0 (b,a,c)
c 0 0 2
a 1 1 1
b 2 1 0 (b,c,a)
c 0 1 2
a 2 1 1
b 2 1 1 (a,c,b)
c 0 2 2
a 2 2 1
b 2 1 2 (c,a,b)
c 1 2 2
a 2 2 2
b 2 2 2 (c,b,a)
c 2 2 2
a 3 2 2
b 2 3 2 (a,b,c)
c 2 2 3
Cateva observatii.
Daca numarul elementelor creste la 4 {a,b,c,d} si aplicam algoritmul, se va vedea pe parcurs ca unele permutari apar de mai multe ori inainte de a se genera toate cele 24 de permutari distincte, dar in final se genereaza toate cele 24 de permutari, plus cateva dubluri. Acest lucru se intampla pentru orice multime de elemente cu cardinal mai mare ca 3.
O alta observatie este ca algoritmul cu unele mici modificari poate fi utilizat si pentru cautarea aranjamentelor sau altor configuratii de elemente.
Comments