1110 Sortari2

[•andrei.12]

Aici puteti discuta despre problema Sortari2.

[•dornescuvlad]

Nu ma prind cum e recurenta pentru :
dp[ i ][ j ] - numarul de permutari de lungime i cu j inversiuni.

dp[ i ][ j ] = dp[i - 1][0] + dp[i - 1][1]  + dp[i - 1][2] + ... dp[i - 1][k] cu k <= j cumva ?

L.E : Sau e  dp[ i ][ j] += i * dp[i - 1][ j ] + dp[ i - 1][ j - 1 ] ?

[•mathboy]

Eu am facut dp[ i ][ j ] = numarul de permutari cu proprietatea ceruta astfel incat sa ai i elemente in permutare care incep cu numarul j.

[•dornescuvlad]

Am gasit o rezolvare cu dinamica aia pe care am spus-o, cu inversiunile, dar nu stiu inca daca e corecta vreuna din recurentele de mai sus.   

[•dornescuvlad]

Sunt curios de ce rezolvarea cu fibonacci este asa cum este.
Poate explica cineva ?

[•filipb]

Numarul de permutari cu timp de sortare egal prin cele doua procedee si care incep cu 1 este fib[2N-3], numarul celor care incep cu 2 este tot fib[2N-3], numarul celor care incep cu 3 este fib[2N-5], cu 4 fib[2N-7]. Avem ca:

Cod:

fib[1] + fib[3] + fib[5] + … + fib[2N-5] + fib[2N-3] + fib[2N-3] = 
fib[2] + fib[3] + fib[5] + … + fib[2N-5] + fib[2N-3] + fib[2N-3] = 
fib[4] + fib[5] + … + fib[2N-5] + fib[2N-3] + fib[2N-3] =
…………………………………………………………. =
fib[2N-2] + fib[2N-3] = fib[2N-1].

Demonstratia se face prin inductie. Cand la o permutare cu N elemente adaugam 1 in fata nu se schimba nimic => numarul permutarilor cu N+1 elemente care incep cu 1 este fib[2N-1]. Cand la o permutare cu N elemente adaugam 2 in fata (crescand cu 1 elementele >= 2), evident numarul inversiunilor creste cu 1 si la fel si numarul ciclurilor => adaugam fib[2N-1] la solutie.
Cand adaugam x (x >= 3), permutarea trebuie sa inceapa astfel: x 1 2 … (x-2) P, unde P este o permutare de lungime N-x+2 care trebuie sa aiba propr. ceruta. Numarul permutarilor P este din ipoteza inductiva fib[2*(N-x+2)-1] = fib[2N-2x+3]. Pentru x = 3, 4, 5.. sumam valori de forma fib[2N-3], fib[2N-5], etc si ajungem in final la o suma de forma:
fib[1] + fib[3] + … + fib[2N-5] + fib[2N-3] + fib[2N-1] + fib[2N-1] = fib[2N+1], ceea ce trebuia demonstrat.

[•dornescuvlad]

Multumesc.Totusi, egalitatile cu fib[2n - 3] pt cele care incep cu 1, fib[2n - 3] pt cele de lungime n care incep cu 2, fib[2n - 5] pt cele de lungime n care incep cu 3 etc. sunt observatii?
Sau are vreo teoretic vreo legatura sirul fibonacci cu ciclul intr-o permutare?

[•filipb]

Dupa ce am observat regulile de formare, eu am demonstrat inductiv ca mai sus. Nu stiu daca are legatura cu ciclurile intr-o permutare in general