Curs 3 Permutari cu repetitie. Combinari. Algoritmi...

Curs 3

Permutari cu repetitie. Combinari.Algoritmi de ordonare si generare

Octombrie 2015

Curs 3 Permutari cu repetitie. Combinari. Algoritmi de ordonare si generare

Cuprins

Algoritmi de ordonare si generare pentru permutari cu repetitie

Reprezentarea binara a submultimilor

B Algoritmi de ordonare si generare

Generarea rapida a combinarilor

B Coduri Gray; propertati

Submultimi ordonate lexicografic

Generarea k-combinarilor


Permutari cu repetitie

r -permutarile cu repetitie ale unui alfabet A = {a1, . . . , an} suntsecventele ordonate de forma

〈x1, . . . , xr 〉

unde x1, . . . , xr ∈ A.

B Acelasi simbol poate sa apara de mai multe ori ın or -permutare cu repetitie

B Conform regulii produsului, exista nr r -permutari cu repetitie


Permutari cu repetitieAlgoritmi de ordonare si generare ın ordine lexicografica

r -permutarile cu repetitie pot fi ordonate lexicografic, la fel ca sir -permutarile obisnuite.

Exemplu (A = {a1, a2} cu a1 < a2, r = 3)

r -permutare cu repetitie a lui A rang〈a1, a1, a1〉 0〈a1, a1, a2〉 1〈a1, a2, a1〉 2〈a1, a2, a2〉 3〈a2, a1, a1〉 4〈a2, a1, a2〉 5〈a2, a2, a1〉 6〈a2, a2, a2〉 7

Definitie (Ordonare lexicografica)

〈x1, . . . , xr 〉 < 〈y1, . . . , yr 〉 daca exista k ∈ {1, . . . , n} astfel ıncat xk < yksi xi = yi pentru toti 1 ≤ i < k .


Ordonarea si generarea r -permutarilor cu repetitieObservatii

Fie A = {a1, a2, . . . , an} cu a1 < a2 < . . . < an.

Daca definim index(ai ) := i − 1 pentru 1 ≤ i ≤ n si ınlocuimai cu index(ai ) ın enumerarea lexicografica a r -permutarilor,avem

r -permutare cu repetitie a lui A rang〈a1, . . . , a1, a1, a1〉 ↔ 〈0, . . . , 0, 0, 0− 1〉 0...

...〈a1, . . . , a1, a1, an〉 ↔ 〈0, . . . , 0, 0, n − 1〉 n − 1〈a1, . . . , a1, a2, a1〉 ↔ 〈0, . . . , 0, 1, 0− 1〉 n...

...〈a1, . . . , a1, a2, an〉 ↔ 〈0, . . . , 0, 1, n − 1〉 2 n − 1...

...

Observatie: r -permutarea cu repetitie a indecsilor estereprezentarea ın baza n a rangului.


Ordonarea si generarea r -permutarilor cu repetitieExercitii

1 Sa se defineasca un algoritm care calculeaza rangul uneir -permutari cu repetitie 〈x1, . . . , xr 〉 a lui A = {1, . . . , n} ınraport cu ordinea lexicografica.

2 Sa se defineasca un algoritm care calculeaza r -permutarea curepetitie a lui A = {1, . . . , n} care are rangul k ın raport cuordinea lexicografica.

3 Sa se defineasca un algoritm care calculeaza r -permutarea curepetitie care urmeaza imediat dupa r -permutarea cu repetitie〈x1, . . . , xr 〉 a lui A.


CombinariReprezentarea binara a submultimilor

O r -combinare a unei multimi A cu n elemente este o submultime cu relemente a lui A.

Exista o correspondenta bijectiva ıntre sirurile de n-biti si submultimilemultimii A = {a1, a2, . . . , an}:

B ⊆ A 7→ bn−1bn−2 . . . b0 unde bi =

{1 daca an−i ∈ B0 ın caz contrar.

sir de n-biti b0b1 . . . bn−1 7→ submultimea {an−i | bi = 1} lui A

Exemplu

A = {a1, a2, a3, a4, a5} unde a1 = a, a2 = b, a3 = c , a4 = d , a5 = e.

∅ ↔ 00000 {a, b} ↔ 00011 {c , d , e} ↔ 11100{a} ↔ 00001 {a, c} ↔ 00101 {b, c , d , e} ↔ 11110{b} ↔ 00010 {a, d} ↔ 01001 {a, b, d , e} ↔ 11011{c} ↔ 00100 {a, e} ↔ 10001 {a, c , d , e} ↔ 11101{d} ↔ 01000 {b, c} ↔ 00110 {a, b, c , d} ↔ 01111{e} ↔ 10000 . . . {a, b, c , d , e} ↔ 11111


Calculul codificarii ca sir binar a lunei submultimi

BitString(B: submultime a lui A,A: multime ordonata {a1, . . . , an})

int bit string[0 ..n − 1]for i:=0 to n − 1 do

if ai ∈ B thenbit string [n − i ] := 1

elsebit string [n − i ] := 0

return bit string


Calcului combinarii corespunzatoare unui sir de n-biti

Combination(b[0..n-1]: sir de biti,

A: multime ordonata {a1, . . . , an})B:=∅for i:=0 to n − 1 do

if b[i ] = 1 thenadauga an−i la B

return B


Ordonarea submultimilor folosind codificari cu siruri binare

Exista o corespondenta bijectiva ıntre codificarile cu siruri binare de n-bitisi numerele cuprinse ıntre 0 si 2n − 1 :

B sir de n−biti b[0 .. n − 1] 7→ numaruln−1∑i=0

b[i ] · 2i

B numar 0 ≤ r < 2n 7→ sirul de n-biti b[0 .. n − 1] unde

b[i ] :=⌊ ci

2i

⌋unde ci este restul ımpartirii lui r cu 2i+1.

Definitie

Rangul unei submultimi B a multimii ordonate A cu n elemente este

Rank(B,A) :=n−1∑i=0

b[i ] · 2i

unde b[0 .. n − 1] este codificarea cu sir de n-biti a lui B ca submultime alui A.


Ordonarea submultimilor unei multimi prin intermediulsirurilor de biti

Exemplu (A = {a0, a1, a2})

submultime codificare binara rangb2b1b0

∅ 000 0{a0} 001 1{a1} 010 2{a0, a1} 011 3{a2} 100 4{a0, a2} 101 5{a1, a2} 110 6{a0, a1, a2} 111 7

Observatie. Acest mod de enumerare a submultimilor uneimultimi de numeste ordonare canonica, iar sirul b2b1b0 se numestecod canonic (sau binar).


Ordonarea submultimilor cu ajutorul sirurilor de biti (2)

B ⊆ 〈a0, . . . , an−1〉

n-biti b[0..n − 1]pentru codificarea binara

n−1∑i=0

b[i ] · 2i

BitString(B,A)

calcul direct

Rank(B,A)


Enumerarea submultimilor prin intermediul reprezentariibinare

Se da o multime ordonata A = {a0, a1, . . . , an−1}, si 0 ≤ r < 2n

Sa se determine submultimea B a lui A cu rangul r

0 ≤ r < 2n

n-bit string encoding b[0 .. n − 1]b[i ] := bc/2ic unde c := r mod 2i+1

pentru 0 ≤ i < n

B := {ai | b[n − i − 1] = 1}

Combination(b,A)

Unrank(A, r)


Enumerarea submultimilor prin intermediul reprezentariibinare

Problema 1:

Se da o submultime B a multimii ordonate A.

Sa se determine submultimea lui A care urmeaza dupa B ın ordonareaprin intermediul reprezentarii binare.

Sugestie: Se poate defini NextBinaryRankSubset(A,B) folosindalgoritmii anteriori de ordonare si enumerare.

Problema 2: Sa se genereze lista tuturor submultimilor lui A ın ordineacrescatoare a rangului calculat prin intermediul codificarii binare.

Sugestie: Se poate folosi functia Unrank(A, r) definita anterior.


Enumerarea submultimilor cu modificari minimeCoduri Grey

Frank Grey a descoperit ın 1953 o metoda de enumerare a tuturorsubmultimilor unei multimi ıntr-o ordine ın care submultimileconsecutive difera prin inserarea sau stergerea unui singur element.

Aceasta schema de enumerare se numeste cod Grey reflectatstandard.

Exemplu

Folosind metoda lui Grey, submultimile of {a, b, c} sunt enumerate ınordinea urmatoare:

{}, {c}, {b, c}, {b}, {a, b}, {a, b, c}, {a, c}, {a}

Codificarile ca siruri binare b0b1b2 ale acestor submultimi sunt:

000, 100, 110, 010, 011, 111, 101, 001


Codul Grey reflectat standardDescriere

Se doreste enumerarea submultimilor multimiiA = {a0, a1, . . . , an−1} ıntr-o ordine cu modificari minime ıntresubmultimi consecutive. Fie Gn lista respectiva.

Procedam recursiv:

1 Se calculeaza lista Gn−1 a submultimilor luiB = {a1, . . . , an−1} ıntr-o ordine Grey cu modificari minime.

2 Fie G ′n−1 lista obtinta prin adaugarea lui a0 la fiecare elemental unei copii inversate a listei Gn−1.

3 Gn este rezultatul concatenarii listei Gn−1 cu G ′n−1.


Propertati ale codurilor Grey reflectate

Se presupune ca B este submultime a multimii ordonate A cu nelemente.Daca

m este rangul lui B in ın ordinea enumerarii lui Grey, sim =

∑n−1i=0 bi · 2i

Codificarea ca sir de n biti a lui B este c0c1 . . . cn−1

atunci

ci = (bi + bi+1) mod 2 for all 0 ≤ i < n, unde bn = 0.

Reciproc, se poate demonstra ca

bi = (ci + ci+1 + . . . + cn−1) mod 2 pentru toti 0 ≤ i < n.


Coduri Grey

Exemplu (A = {a, b, c} cu a < b < c)

submultime rang Grey b0b1b2 sir de biti rangB m astfel ıncat al lui B al lui B

m =∑2

i=0 b2−i2i c0c1c2

{} 0 000 000 0{c} 1 100 100 4{b, c} 2 010 110 6{b} 3 110 010 2{a, b} 4 001 011 3{a, b, c} 5 101 111 7{a, c} 6 011 101 5{a} 7 111 001 1

Se observa ca ci = (bi + bi+1) mod 2 pentru toti 0 ≤ i < 3, undeb3 = 0.


Exercitii

1 Folositi ecuatiile de pe slide-ul precedent ca sa implementatimetodele de ordonare RankGrey(B,A) si de enumerareUnrankGrey(A,r) pentru enumerarea submultimilor bazatape coduri Grey.

2 Sa se definesca metoda NextGreyRankSubset(A,B) carecalculeaza submultimea lui A care urmeaza imediat dupasubmultimea B ın enumerarea submultimilor bazata pe coduriGrey.


k-combinariGenerarea k-combinarilor

Se da o multime ordonata A cu n elemente si 0 ≤ k ≤ n.

Sa se genereze toate k-combinarile lui A.

Metoda 1 (naiva si ineficienta): generare si testare

1 Se genereaza toate cele 2n submultimi ale lui A

2 Se elimina submultimile generate care nu au k elemente.

Metoda 2 (recursie simpla): Daca A = {a} ∪ B unde a 6∈ B estecel mai mic element al lui A atunci

1 Genereaza lista L1 a tuturor (k − 1)-combinarilor lui B, si fieL2 lista tuturor k-combinarilor lui B.

2 Fie L3 lista ce se obtine adaugand a la toate elementele lui L1.

3 Returneaza rezultatul concatenarii listelor L2 si L3.


Ordonarea lexicografica a k-combinarilorEnuntul problemei. Observatii preliminare (1)

Se presupune ca A = {1, 2, . . . , n} si X = {x1, x2, . . . , xk} ⊆ A astfelıncat x1 < x2 < . . . < xk .

I: Care este rangul lui X ın enumerarea lexicografica a k-combinarilorlui A?

k-combinarile care apar ınaintea lui X ın ordine lexicografica sunt de 2feluri:

1 Cele care contin un element mai mic decat x1.

2 Cele al caror element minim este x1, dar restul elementelor este o(k − 1)-combinare mai mica decat {x2, x3, . . . , xk}.

⇒ rangul lui X ın enumerarea lexicografica a k-combinarilor lui A esteN1 + N2 unde

B N1 este numarul k-combinarilor de primul fel

B N2 este numarul k-combinarilor de al doilea fel


Ordonarea lexicografica a k-combinarilorObservatii preliminare (2)

Ipoteza: A = {1, 2, . . . , n}.Cum putem calcula N1?

Numarul k-combinarilor lui A care au pe i cel mai mic element este

(n−ik−1

)⇒ N1 =

∑x1−1i=1

(n−ik−1

)(regula sumei)

Stim ca(nk

)=(n−1k−1

)+(n−1k

)(vezi curs 1)

⇒ N1 =∑x1−1

i=1

((n−i+1

k

)−(n−ik

))=(nk

)−(n−x1+1

k

)

Cum putem calcula N2?

N2 este rangul lui {x2, . . . , xk} ın enumerarea lexicografica a(k − 1)-combinarilor lui {x1 + 1, x1 + 2, . . . , n − 1, n}

⇒ N2 se poate calcula recursiv.




Numarul k-combinarilor lui A care au pe i cel mai mic element este

(n−ik−1

)⇒ N1 =

∑x1−1i=1

(n−ik−1

)(regula sumei)

Stim ca(nk

)=(n−1k−1

)+(n−1k

)(vezi curs 1)

⇒ N1 =∑x1−1

i=1

((n−i+1

k

)−(n−ik

))=(nk

)−(n−x1+1

k

)Cum putem calcula N2?






Numarul k-combinarilor lui A care au pe i cel mai mic element este(n−ik−1

)

⇒ N1 =∑x1−1

i=1

(n−ik−1

)(regula sumei)

Stim ca(nk

)=(n−1k−1

)+(n−1k

)(vezi curs 1)

⇒ N1 =∑x1−1

i=1

((n−i+1

k

)−(n−ik

))=(nk

)−(n−x1+1

k







Numarul k-combinarilor lui A care au pe i cel mai mic element este(n−ik−1

)⇒ N1 =

∑x1−1i=1

(n−ik−1

)(regula sumei)

Stim ca(nk

)=(n−1k−1

)+(n−1k

)(vezi curs 1)

⇒ N1 =∑x1−1

i=1

((n−i+1

k

)−(n−ik

))=(nk

)−(n−x1+1

k





Ordonarea lexicografica a k-combinarilor

Din observatiile anterioare rezulta urmatoarea implementare recursiva aoperatiei de calcul al rangului:

RankKSubset({x1, . . . , xk}, {`, . . . , n}) calculeaza rangul ın ordinelexicografica a k-combinarii {x1, . . . , xk} a multimii ordonate{`, ` + 1, . . . , n − 1, n}. Se presupune ca x1 < x2 < . . . < xk .

RankKSubset({x1, . . . , xk}, {`, ` + 1, . . . , n})if (n = k or k=0)

return 0,

p := x1 − ` + 1if (k = 1)

return p − 1else

return(nk

)−(n−p+1

k

)+ RankKSubset({x2, . . . , xk}, {x1 + 1, . . . , n})


Enumerarea lexicografica a k-combinarilorEnuntul problemei. Observatii preliminare

Ipoteze:

A = {1, 2, . . . , n} si X = {x1, x2, . . . , xk} cu x1 < x2 < . . . < xk estesubmultimea lui A cu rangul m ın enumerarea lexicografica a tuturork-combinarilor lui A.[Retinem ca 0 ≤ m <

(nk

).]

I: Care sunt valorile lui x1, x2, . . . , xk?



1 Numarul total al k-combinarilor lui A care contin un element < x1 este

x1−1∑i=1

(n − i

k − 1

)=(nk

)−(n − x1 + 1

k

)≤ m. (1)

unde(n−ik−1

)este numarul k-combinarilor ın care cel mai mic element este

i ∈ {1, . . . , x1 − 1}. Acest numar este ≤ m fiindca toate aceste k-combinari sunt

lexicografic mai mici decat X , care are rangul m.

2 Numarul total al k-combinarilor lui A care contin un element ≤ x1 este

x1∑i=1

(n − i

k − 1

)=(nk

)−(n − x1

k

)> m. (2)

unde(n−ik−1


i ∈ {1, . . . , x1}. Acest numar este > m deoarece sunt m + 1 ıntregi i ıntre 0 si

rangul lui X (care este m), si toate k-combinarile cu un astfel de rang i contin

un element ≤ x1.

⇒ putem folosi (1) si (2) ca sa aflam x1:(nk

)−(n−x1+1

k

)≤ m <

(nk

)−(n−x1

k

)Celelalte elemente x2, . . . , xk se pot determina recursiv.




x1−1∑i=1

(n − i

k − 1

)=(nk

)−(n − x1 + 1

k

)≤ m. (1)

unde(n−ik−1





x1∑i=1

(n − i

k − 1

)=(nk

)−(n − x1

k

)> m. (2)

unde(n−ik−1




un element ≤ x1.


)−(n−x1+1

k

)≤ m <

(nk

)−(n−x1

k

)

Celelalte elemente x2, . . . , xk se pot determina recursiv.




x1−1∑i=1

(n − i

k − 1

)=(nk

)−(n − x1 + 1

k

)≤ m. (1)

unde(n−ik−1





x1∑i=1

(n − i

k − 1

)=(nk

)−(n − x1

k

)> m. (2)

unde(n−ik−1




un element ≤ x1.


)−(n−x1+1

k

)≤ m <

(nk

)−(n−x1

k

)Celelalte elemente x2, . . . , xk se pot determina recursiv.


Enumerarea lexicografica a k-combinarilor

UnrankKSubset(m, k , {a1, . . . , an}) produce k-combinarea{x1, . . . , xk} cu rangul m a lui {a1, . . . , an} ın ordine lexicografica.Se presupune ca x1 < . . . < xk si a1 < . . . < an.

UnrankKSubset(m, k, {a1, . . . , an})if (k = 1)

return ak+1

else if (m = 0)return {a1, . . . , am}

elseu :=

(nk

)i := 1while

( ik

)< u −m

i++x1:=n − (i − 1)

return {an−i+1} ∪ UnrankKSubset(m − u +(n−x1+1

k

), k − 1,{an−i+2, . . . , an})


Bibliografie

S. Pemmaraju, S. Skiena. Combinatorics and Graph Theorywith Mathematica. Section 2.3: Combinations. CambridgeUniversity Press. 2003.


Curs 3 Permutari cu repetitie. Combinari. Algoritmi...

Documents

Transcript of Curs 3 Permutari cu repetitie. Combinari. Algoritmi...