generarea si ordonarea permutarilor. principiul...

Generarea si ordonarea permutarilor.Principiul porumbeilor.

Principiul incluziunii si excluziunii

Generarea si ordonarea permutarilor. Principiul porumbeilor. Principiul incluziunii si excluziunii

Recapitulare din cursul trecut

Presupunem ca A este o multime cu n elemente.

B Un aranjament de n luate cate r (sau r -permutare) a lui Aeste o secventa ordonata de elemente din A.

B O permutare a lui A este o secventa ordonata a tuturorelementelor din A.

B O combinare de n luate cate r a lui A este o submultime cu relemente din A.

Exemplu (A = {a1, a2, a3})B 2-permutarile lui A sunt (ordinea conteaza!):

〈a1, a2〉, 〈a2, a1〉, 〈a1, a3〉, 〈a3, a1〉, 〈a2, a3〉, 〈a3, a1〉

B 2-combinarile lui A sunt (ordinea nu conteaza!):

{a1, a2}, {a1, a3}, {a2, a3}

B Permutarile lui A sunt:

〈a1, a2, a3〉, 〈a1, a3, a2〉, 〈a2, a1, a3〉, 〈a2, a3, a1〉,〈a3, a1, a2〉, 〈a3, a2, a1〉

〈a1, a2〉, 〈a2, a1〉, 〈a1, a3〉, 〈a3, a1〉, 〈a2, a3〉, 〈a3, a1〉

{a1, a2}, {a1, a3}, {a2, a3}

〈a1, a2〉, 〈a2, a1〉, 〈a1, a3〉, 〈a3, a1〉, 〈a2, a3〉, 〈a3, a1〉

{a1, a2}, {a1, a3}, {a2, a3}

〈a1, a2〉, 〈a2, a1〉, 〈a1, a3〉, 〈a3, a1〉, 〈a2, a3〉, 〈a3, a1〉

{a1, a2}, {a1, a3}, {a2, a3}

〈a1, a2〉, 〈a2, a1〉, 〈a1, a3〉, 〈a3, a1〉, 〈a2, a3〉, 〈a3, a1〉

{a1, a2}, {a1, a3}, {a2, a3}

Exemplu (A = {a1, a2, a3})B 2-permutarile lui A sunt (ordinea conteaza!):〈a1, a2〉, 〈a2, a1〉, 〈a1, a3〉, 〈a3, a1〉, 〈a2, a3〉, 〈a3, a1〉

{a1, a2}, {a1, a3}, {a2, a3}

B 2-combinarile lui A sunt (ordinea nu conteaza!):{a1, a2}, {a1, a3}, {a2, a3}

B Permutarile lui A sunt:〈a1, a2, a3〉, 〈a1, a3, a2〉, 〈a2, a1, a3〉, 〈a2, a3, a1〉,〈a3, a1, a2〉, 〈a3, a2, a1〉

Operatii cu aranjamente si permutari

In prima parte a acestui curs vom ınvata:

Cum sa ordonam permutarile ıncat sa putem vorbi despreprima permutare, a doua, etc.

Cum sa generam permutarea care urmeaza dupa o permutaredata

Cum sa generam direct a k-a permutare

Cum sa determinam a cata este o permutare data

Relatii de ordine pentru r -permutari

Presupunem ca A este o multime finita cu n elemente.1 Mai ıntai ordonam elementele multimii A

⇒ A = {a1, a2, . . . , an} undea1 = primul element. . .an = al n-lea element.

⇒ A devine o multime ordonata (un alfabet) ın carea1 < a2 < . . . < an.

2 r -permutarile sunt cuvinte 〈b1, ..., br 〉 de lungime r pe care leordonam ca si cuvintele din dictionar, de exemplu:

〈a1, a2〉 < 〈a1, a3〉 < 〈a2, a1〉 < . . .

Aceasta ordonare a r -permutarilor se numeste ordonarelexicografica:

〈b1, . . . , br 〉 < 〈c1, . . . , cr 〉 daca exista o pozitie k astfel ıncatbi = ci pentru 1 ≤ i < k , si bk < ck .

Relatii de ordine pentru r -permutariObservatii preliminare

Fie A = {a1, . . . , an} o multime ordonata cu a1 < . . . < ansi N = {1, 2, . . . , n}.

1 r -permutarile lui A sunt cuvinte de forma 〈ai1 , . . . , air 〉 cui1, . . . , ir ∈ N.

2 〈ai1 , . . . , air 〉 este o r -permutare a lui A daca si numai daca(i1, . . . , ir ) este o r -permutare a lui N.

3 〈ai1 , . . . , air 〉 < 〈aj1 , . . . , ajr 〉 daca si numai daca〈i1, . . . , ir 〉 < 〈j1, . . . , jr 〉.

⇒ este suficient sa stim cum sa ordonam si sa enumeramr -permutari de numere din multimea N.

De acum ıncolo vom considera doar r-permutari ale multimiiordonate A = {1, . . . , n}.

Rangul unei r -permutari

Rangul unei r -permutari este pozitia la care apare r -permutarea ınordine lexicografica, pornind de la pozitia 0.

Exemplu (A = {1, 2, 3})

2-permutare rang permutare rang

〈1, 2〉 0 〈1, 2, 3〉 0〈1, 3〉 1 〈1, 3, 2〉 1〈2, 1〉 2 〈2, 1, 3〉 2〈2, 3〉 3 〈2, 3, 1〉 3〈3, 1〉 4 〈3, 1, 2〉 4〈3, 2〉 5 〈3, 2, 1〉 5

Enumerarea permutarilor ın ordine lexicografica

Problema

Cum putem calcula permutarea lui N = {1, . . . , n} care urmeazadupa permutarea 〈p1, . . . , pn〉 ın ordine lexicografica?

Exemplu (N = {1, 2, 3, 4, 5})

permutare permutare urmatoare

〈5, 1, 3, 2, 4〉

〈5, 1, 3, 4, 2〉

〈5, 2, 4, 3, 1〉

〈5, 3, 1, 2, 4〉

〈5, 4, 3, 2, 1〉

nu exista

Permutarea care urmeaza dupa 〈p1, . . . , pn〉 se poate calcula astfel:

1 Determina i astfel ıncat pi > . . . > pn este cel mai lung sufixdescrescator al permutarii 〈p1, . . . , pn〉

2 Detemina j ≥ i astfel ıncat pj este cel mai mic numar mai maredecat pi−1.

3 Permuta pj cu pi−1, si apoi inverseaza sufixul pi , . . . , pn.

Problema

Exemplu (N = {1, 2, 3, 4, 5})

〈5, 1, 3, 2, 4〉〈5, 1, 3, 4, 2〉〈5, 2, 4, 3, 1〉

〈5, 3, 1, 2, 4〉

〈5, 4, 3, 2, 1〉

nu exista

Problema

Exemplu (N = {1, 2, 3, 4, 5})

〈5, 1, 3, 2, 4〉〈5, 1, 3, 4, 2〉〈5, 2, 4, 3, 1〉〈5, 3, 1, 2, 4〉〈5, 4, 3, 2, 1〉

nu exista

Problema

Exemplu (N = {1, 2, 3, 4, 5})

〈5, 1, 3, 2, 4〉〈5, 1, 3, 4, 2〉〈5, 2, 4, 3, 1〉〈5, 3, 1, 2, 4〉〈5, 4, 3, 2, 1〉 nu exista

Problema

Exemplu (N = {1, 2, 3, 4, 5})

〈5, 1, 3, 2, 4〉〈5, 1, 3, 4, 2〉〈5, 2, 4, 3, 1〉〈5, 3, 1, 2, 4〉〈5, 4, 3, 2, 1〉 nu exista

Problema

Exemplu (N = {1, 2, 3, 4, 5})

〈5, 1, 3, 2, 4〉〈5, 1, 3, 4, 2〉〈5, 2, 4, 3, 1〉〈5, 3, 1, 2, 4〉〈5, 4, 3, 2, 1〉 nu exista

Problema

Exemplu (N = {1, 2, 3, 4, 5})

〈5, 1, 3, 2, 4〉〈5, 1, 3, 4, 2〉〈5, 2, 4, 3, 1〉〈5, 3, 1, 2, 4〉〈5, 4, 3, 2, 1〉 nu exista

Problema

Exemplu (N = {1, 2, 3, 4, 5})

〈5, 1, 3, 2, 4〉〈5, 1, 3, 4, 2〉〈5, 2, 4, 3, 1〉〈5, 3, 1, 2, 4〉〈5, 4, 3, 2, 1〉 nu exista

Operatii cu permutariEnumerarea permutarilor ın ordine lexicografica

Exemplu

〈5, 2, 4, 3, 1〉〈5, 3, 4, 2, 1〉

〈p1, p2, p3, p4, p5〉 = 〈5, 2, 4, 3, 1〉

i = 3 j = 4

permuta pi−1 = 2 cu pj = 3

inverseaza 〈pi , . . . , pn〉 = 〈4, 2, 1〉〈5, 3, 1, 2, 4〉 = permutarea urmatoare

Exemplu

〈5, 2, 4, 3, 1〉

〈5, 3, 4, 2, 1〉

〈p1, p2, p3, p4, p5〉 = 〈5, 2, 4, 3, 1〉

Exemplu

〈5, 2, 4, 3, 1〉

〈5, 3, 4, 2, 1〉

〈p1, p2, p3, p4, p5〉 = 〈5, 2, 4, 3, 1〉

i = 3 j = 4

Exemplu

〈5, 2, 4, 3, 1〉

〈5, 3, 4, 2, 1〉

〈p1, p2, p3, p4, p5〉 = 〈5, 2, 4, 3, 1〉

inverseaza 〈pi , . . . , pn〉 = 〈4, 2, 1〉

〈5, 3, 1, 2, 4〉 = permutarea urmatoare

Exemplu

〈5, 2, 4, 3, 1〉〈5, 3, 4, 2, 1〉

〈p1, p2, p3, p4, p5〉 = 〈5, 2, 4, 3, 1〉

i = 3 j = 4

inverseaza 〈pi , . . . , pn〉 = 〈4, 2, 1〉

〈5, 3, 1, 2, 4〉 = permutarea urmatoare

Enumerarea permutarilor ın ordine lexicograficaPseudocod

PermutareUrmatoare(p: int[0 .. n − 1])i := n − 2;while (p[i ] > p[i + 1])

i--;j := n − 1;while (p[j ] < p[i ])

j--;// permuta valorile lui p[i ] si p[j ]tmp := p[i ];p[i ] := p[j ];p[j ] := tmp;// inverseaza (p[i+1], ..., p[n-1])

for (k := 0; k < b(n − i − 1)/2c; k++)// swap p[i + 1 + k] with p[n − 1− k]tmp := p[i + 1 + k];p[i + 1 + k] := p[n − 1− k];p[n − 1− k] := tmp;

return p;

Operatii cu permutari

Probleme

1 Cum putem calcula direct si eficient rangul unei permutari〈p1, . . . , pn〉 a lui N = {1, . . . , n} ıntr-o enumerarelexicografica?

2 Cum putem calcula direct si eficient permutarea 〈p1, . . . , pn〉lui N = {1, . . . , n} care are rangul k?Presupunem ca 0 ≤ k < n!

Calculul rangului unei permutari

Fie r rangul permutarii 〈p1, . . . , pn〉.B Daca p1 = 1 atunci 0 ≤ r < (n − 1)!B Daca p1 = 2 atunci (n − 1)! ≤ r < 2 · (n − 1)!

. . .B Daca p1 = k atunci (k − 1) · (n − 1)! ≤ r < k · (n − 1)!

. . .B Daca p1 = n atunci (n − 1) · (n − 1)! ≤ r < n · (n − 1)! = n!

⇒ ın general, (p1 − 1) · (n − 1)! ≤ r < p1 · (n − 1)!

⇒ rangul lui 〈p1, . . . , pn〉 = (p1 − 1) · (n − 1)! +rangul lui 〈p2, . . . , pn〉 ınenumerarea lexicograficaa permutarilor lui N − {p1}

⇒ r se poate calcula recursiv.

⇒ ın general, (p1 − 1) · (n − 1)! ≤ r < p1 · (n − 1)!

Exemplu

Permutarea 〈p1, p2, p3, p4, p5〉 = 〈2, 3, 1, 5, 4〉 are rangul

r = (2− 1) · (5− 1)!+ rangul lui 〈3, 1, 5, 4〉 ın ordonarealexicografica a permutarilor lui {1, 3, 4, 5}.

rangul lui 〈3, 1, 5, 4〉 ın ordonarea lexicografica a permutarilorlui {1, 3, 4, 5} este acelasi curangul lui 〈2, 1, 4, 3〉 ın ordonarea lexicografica a permutarilorlui {1, 2, 3, 4}

(am micsorat cu 1 toate elementele mai mari decat p1 = 2)

Procedand recursiv, vom obtine ca rangul lui 〈2, 1, 4, 3〉 este 7.

⇒ rangul lui 〈2, 3, 1, 5, 4〉 este 24 + 7 = 31.

Calculul rangului unei permutariPseudocod

Rang(p : int[0 .. n − 1])if n == 1

return 0

elseq : int[0 .. n − 2];// ajusteaza p[1..n-1] sa fie permutare a lui {1, ..., n − 1}// memorata in q[0 .. n − 2]for(i := 1; i ≤ n − 1; i++)

if(p[i ] < p[0])q[i − 1] = p[i ];

elseq[i − 1] = p[i ]− 1;

return Rang[q] + (p[0]− 1) · (n − 1)!

Calculul unei permutari cu rang dat

Se doreste un algoritm care construieste direct permutarea(p1, . . . , pn) cu rangul r , cand 0 ≤ r < n!.

Am observat deja ca daca permutarea (p1, . . . , pn) are rangulr , atunci (p1 − 1) · (n − 1)! ≤ r < p1 · (n − 1)!

⇒ p1 =

(n − 1)!

⌋+ 1

⇒ Daca (q1, . . . , qn−1) este permutarea cu rangulr − (p1 − 1) · (n − 1)! atunci

pi+1 =

{qi daca qi < p1,qi + 1 daca qi ≥ p1.

pentru fiecare subsecventa.

Algoritmi de generare rapida a tuturor permutarilor(Optional)

Generarea tuturor permutarilor se poate face si ın alta ordinedecat cea lexicografica.

Uneori se doreste generarea foarte rapida a tuturorpermutarilor:

B Acest lucru este posibil daca fiecare permutare se obtine foarterapid din cea precedenta.

B In 1963, Heap a descoperit un algoritm care genereazapermutarea urmatoare a unei permutari prin interschimbareavalorilor a 2 elemente.

Algoritmul lui Heap este cel mai rapid algoritm degenerare a tuturor permutarilor.

Generarea rapida a permutarilor cu algoritmul lui Heap(Optional)

for(i := 1; i ≤ n; i++)p[i ] := i

for(c := 1; c ≤ n; c++)1. genereaza toate permutarile lui 〈p[1], . . . , p[n − 1]〉 fara a-l modifica pe p[n];(la sfarsitul pasului 1, p contine ultima permutare generata)2. permuta p[n] cu elementul p[f (n, c)]

unde f (n, c) =

{1 daca n este impar,c daca n este par.

B Algoritmul lui Heap genereaza toate permutarile lui {1, . . . , n} ıntr-o ordinediferita de cea lexicografica.

B Fiecare permutare difera de cea precedenta printr-o transpozitie (adica, ointerschimbare a valorilor a 2 elemente).

Exemplu

Algoritmul lui Heap enumera permutarile lui {1, 2, 3} ın ordinea urmatoare:

〈1, 2, 3〉, 〈2, 1, 3〉, 〈3, 1, 2〉, 〈1, 3, 2〉, 〈2, 3, 1〉, 〈3, 2, 1〉

for(i := 1; i ≤ n; i++)p[i ] := i

unde f (n, c) =

Exemplu

〈1, 2, 3〉, 〈2, 1, 3〉, 〈3, 1, 2〉, 〈1, 3, 2〉, 〈2, 3, 1〉, 〈3, 2, 1〉

for(i := 1; i ≤ n; i++)p[i ] := i

unde f (n, c) =

Exemplu

〈1, 2, 3〉, 〈2, 1, 3〉, 〈3, 1, 2〉, 〈1, 3, 2〉, 〈2, 3, 1〉, 〈3, 2, 1〉

for(i := 1; i ≤ n; i++)p[i ] := i

unde f (n, c) =

Exemplu

〈1, 2, 3〉, 〈2, 1, 3〉, 〈3, 1, 2〉, 〈1, 3, 2〉, 〈2, 3, 1〉, 〈3, 2, 1〉

Exercitii

1 Sa se implementeze un program care citeste o secventa de nnumere si apoi afiseaza:

”este permutare” daca secventa respectiva este o permutare alui {1, . . . , n}”nu este permutare” ın caz contrar.

2 Sa se implementeze un program care citeste numerele n sir ∈ {0, 1, . . . , n!− 1} si afiseaza permutarea lui {1, . . . , n}care are rangul r .

3 Sa se implementeze un program care citeste o permutare a lui{1, . . . , n} si afiseaza rangul permutarii respective.

4 Scrieti un program care citeste o permutare 〈a1, . . . , an〉 sicalculeaza inversa ei, adica permutarea 〈b1, . . . , bn〉 astfelıncat bai = abi = i pentru orice 1 ≤ i ≤ n.

Exercitii

1 Scrieti un program care citeste o permutare si calculeazapermutarea urmatoare ın ordine lexicografica.

2 Scrieti un program care citeste o permutare si calculeazapermutarea precedenta ın ordine lexicografica.

Principiul porumbeilor

Exemplu

Presupunem ca un card de 13 porumbei ocupa o cusca cu 12adaposturi.

Numarul de adaposturi este mai mic decat numarul de porumbei ⇒cel putin un adapost va fi ocupat de cel putin 2 porumbei.

Principiul porumbeilor (sau Principiul lui Dirichlet)

Fie n un numar ıntreg pozitiv. Daca mai mult de n obiecte suntdistribuite ın n containere, atunci un container trebuie sa contina celputin 2 obiecte.

Exemplu

Presupunem ca un card de 13 porumbei ocupa o cusca cu 12adaposturi.

Numarul de adaposturi este mai mic decat numarul de porumbei ⇒cel putin un adapost va fi ocupat de cel putin 2 porumbei.

Principiul porumbeilor (sau Principiul lui Dirichlet)

Fie n un numar ıntreg pozitiv. Daca mai mult de n obiecte suntdistribuite ın n containere, atunci un container trebuie sa contina celputin 2 obiecte.

Principiul porumbeilorApplicatii ın rationamentul combinatorial

Stabilirea existentei unei anumite configuratii sau combinari ındiverse situatii.

1 Presupunem ca sunt 367 studenti ınscrisi la cursul de istorie.Atunci cel putin 2 studenti au aceeasi zi de nastere.

Demonstratie. Numarul de studenti este mai mare decatnumarul de zile calendaristice. Conform pricipiului porumbeilor,cel putin 2 studenti sunt nascuti ın aceeasi zi calendaristica.

2 n pugilisti concureaza ıntr-un turneu care prevede un meciıntre fiecare pereche de pugilisti. Fiecare pugilist a pierdut celputin un meci. Atunci cel putin 2 pugilisti au obtinut acelasinumar de victorii.

Demonstratie. Sunt n pugilisti, si fiecare pugilist are ıntre 0si n − 2 victorii. (Observati ca nici un pugilist nu are n − 1victorii deoarece stim ca fiecare a pierdut cel putin un meci.)Conform principiului porumbeilor, cel putin 2 pugilisti auacelasi numar de victorii.

Generalizare: Fie m si n ıntregi pozitivi. Daca mai mult decat m · nobiecte sunt distribuite ın n containere, atunci cel putin un container

trebue sa contina cel putin m + 1 obiecte.

Demonstratie: prin contradictie. Daca punem cel mult m

obiecte ın fiecare container, atunci numarul total de obiecte ar fi cel

mult m · n.

Teorema

Daca a1, a2, . . . , an ∈ R si µ =a1 + a2 + . . .+ an

n, atunci exista ıntregii i

si j cu 1 ≤ i , j ≤ n astfel ıncat ai ≤ µ si aj ≥ µ.

Demonstratie: prin contradictie.Daca fiecare element este strict mai mare decat µ atunci

µ = (a1 + a2+ . . . +an)/n >n · µn

= µ, contradictie ⇒ ∃ai ≤ µ.

Daca fiecare element este strict mai mic decat µ atunci

µ = (a1 + a2+ . . . +an)/n <n · µn

= µ, contradictie ⇒ ∃aj ≥ µ.

Principiul porumbeilorAplicatia 1: Subsecvente monotone

Definitie (Secventa monotona)

O secventa a1, a2, . . . , an este

crescatoare daca a1 ≤ a2 ≤ . . . ≤ an

strict crescatoare daca a1 < a2 < . . . < an

descrescatoare daca a1 ≥ a2 ≥ . . . ≥ an

strict descrescatoare daca a1 > a2 > . . . > an

Fie secventa 3, 5, 8, 10, 6, 1, 9, 2, 7, 4.

Care sunt subsecventele crescatoare de lungime maxima?

(3, 5, 8, 10), (3, 5, 8, 9), (3, 5, 6, 7), (3, 5, 6, 9)

Care sunt subsecventele descrescatoare de lungime maxima?

(10, 9, 7, 4)

Principiul porumbeilorAplicatia 1: Subsecvente monotone (continuare)

Teorema

Presupunem ca m, n ∈ N− {0}. O secventa cu mai mult de m · n numere

reale trebuie sa contina fie o subsecventa crescatoare de lungime cel putin

m + 1, sau o subsecventa strict descrescatoare de lungime cel putin n + 1.

Demonstratie.r1, r2, . . . , rm·n+1

Pentru fiecare 1 ≤ i ≤ m · n + 1, fie

ai :=lungimea celei mai lungi subsecvente crescatoare ce ıncepe cu ridi :=lungimea celei mai lungi subsecvente strict descrescatoare ceıncepe cu ri

De exemplu, daca secventa este 3, 5, 8, 10, 6, 1, 9, 2, 7, 4 atunci

a2 = 3 (pentru subsecventa 5, 8, 10 sau 5, 8, 9)d2 = 2 (pentru subsecventa 5, 1 sau 5, 2 sau 5, 4)

Principiul porumbeilorAplicatia 1: Subsecvente monotone (Demo. continuata)

Presupunem ca teorema este falsa ⇒ 1 ≤ ai ≤ m si1 ≤ di ≤ n

⇒ perechea (ai , di ) are m · n valori posibile.

Exista m · n + 1 perechi ⇒ ∃i < j cu (ai , di ) = (aj , dj).Daca i < j si (ai , di ) = (aj , dj) atunci

1 Lungimea maxima a subsecventelor crescatoare ce pornesc dinri si din rj este ai .

2 Lungimea maxima a subsecventelor strict descrescatoare cepornesc din ri si din rj este di .

Acest lucru este imposibil fiindca

1 daca ri ≤ rj atunci ri ≤lungime ai︷︸︸︷rj ≤ . . .︸︷︷︸

lungime ai+1

2 Daca ri > rj atunci ri >

lungime di︷︸︸︷rj > . . .︸︷︷︸

lungime di+1

Principiul porumbeilorAplicatia 2: Aproximarea cu numere rationale

Pentru fiecare numar real x ∈ R definim:

bxc := cel mai mare ıntreg m astfel ıncat m ≤ x .

dxe := cel mai mic ıntreg m astfel ıncat x ≤ m.

Partea fractionara a lui x :{x} := x − bxcUn numar irational este un numar care nu este rezultatulımpartirii a doi ıntregi.