Clasa a VII-a lecția 13 - 5 dec 2019

From Algopedia
Jump to navigationJump to search

Anunțuri

  • Din nou mă obligați să fac poliție, de data aceasta cu surse copiate. OK. Ați trezit gigantul care doarme.
  • Avertismente următorilor pentru cod identic: Benescu, Petcu, Ștefănescu. Pentru Petcu este și ultimul avertisment.
  • Învățați să citiți întregi folosind fgetc(). Codul vostru nu este nici eficient și nici robust: un spațiu în plus, sau un \n în minus vă duce la buclă infinită!

Tema - rezolvări

Comentarii generale

  • Încă mai văd avertismente de compilare serioase, variabile neinițializate.
  • Încă văd foarte des return în mijlocul funcției.
  • Voi începe măsurile punitive: dacă văd avertismente seroiase de compilare sau instrucțiuni return în mijlocul funcției voi da 0 pe acea problemă, cu avertisment.
  • Aceeași se scrie cu doi e și nu aceiași (gen aceeași problemă). Creare se scrie cu un singur e și nu creeare. Regulă de verificare: a crea are întotdeauna un e în plus față de a lucra. Lucrez - creez, lucrare - creare, lucrăm - creăm (nu creem), etc.

Unific

Problema unific a fost dată la OJI 2013 clasa a 7a. Problema definește o procedură prin care două numere pot fi unificate, dacă au măcar o cifră în comun. Apoi cere să se aplice pe un vector unificări de elemente adiacente pînă ce nu se mai poate unifica nimic. Întotdeauna se va face prima unificare posibilă de la începutul vectorului.

Comentarii generale

  • Avertismente celor ce nu au trimis nici o rezolvare: Aizic, Mocanu, Cadîr, Ipate.
  • V-am rugat să scrieți cod elegant, fără repetiții, ne-tractor. N-ați vrut, sau nu ați putut? Ambele sînt aproape la fel de grave.

Comentarii individuale

  • Benescu: Ai time limit exceeded. Destul de grav pentru o problemă de genul acesta, unde nu ai cum să intri în cazuri de buclă infinită. Pare că te-ai grăbit să scapi de temă. De ce nu ai depanat programul? Codul este rezonabil, dar e stufos și cu multe repetiții de cod, probabil de aceea ratezi cazuri particulare.
  • Burac: Cod care are sens, dar stufos, cu multe repetiții. Nu numai că folosești două stegulețe, dar mai sînt și globale, folosite și în main și în funcție. Foarte periculos. Genul de cod care este destinat să nu funcționeze pentru că va pierde cazuri particulare.
  • Calotă: Mulțumesc pentru comentarii. Bravo, parsing corect! Ai folosit funcții pentru organizarea codului. Dar nu și pentru a nu duplica cod, ai în continuare repetiții. Organizarea a ajutat, aproape ai luat 100p. Am văzut că ai continuat munca după ce s-a terminat tema, bravo!
  • Chivu: program rezonabil, organizat. Ai cam multe repetiții de cod, de exemplu comun() și unific() descompun cifrele în vectori de frecvență. Cred că funcția comun() ratează cazul cînd x sau y sînt zero, posibil și aici să pierzi puncte.
  • Dimulescu: Cod rezonabil, foarte stufos. Probabil de aceea ratezi anumite cazuri particulare. Ai avertismente de compilare! Setează -O2 și -Wall!
  • Fares: ai instrucțiuni return în mijlocul funcției. Este complet nestructurat și total neacceptat la IQ Academy. Pe așa ceva nu discut, îți pierzi selecția la IQ Academy. Avertisment! Ca observații, ai foarte multe cazuri particulare și zero comentarii. Cu astfel de stil programul este destinat să nu meargă.
  • Iordache: tu nici nu ai încercat problema. Ai trimis rezolvarea la punctul 1, problemă de clasa a cincea. La punctul doi ai făcut doar calculul vectorilor de frecvență ale numerelor. Iordache! Ne supărăm, tema nu a fost mare!
  • Marcu: ai avertismente serioase de compilare, variabile neinițializate. Setează -O2 și -Wall! Programul arată ordonat. Ai ceva repetiții de cod, dar nu exagerate. Păcat că nu l-ai depanat (testele sînt descărcabile acum, repară-l). Ca observație, codul:
int comun( int  x, int  y ) { //returneaza 1 daca au cifre comune, 0 daca nu au
    int c;
    for ( c = 0; c <= 9; c++ )
        vfc[c] = 0;
    if ( x == 0 )
      vfc[0] = 1;
    else
        while ( x > 0 ) {
            vfc[x % 10] = 1;
            x /= 10;
        }
    if ( y == 0 && vfc[0] == 1 )
      return 1;
    while ( y > 0 ) {
        if ( vfc[y % 10] == 1 )
          return 1;
        y /= 10;
    }
    return 0;
}

În primul rînd are return în mijlocul funcției. Mai rău! Este într-o buclă! Mai nestructurat de atît nu se poate! În al doilea rînd, funcția repetă o mare bucată din unific(). De ce să nu calculezi direct vectorul care conține 2 pentru cifrele comune? Dacă apare măcar un doi returnezi 1, altfel 0. Funcția se putea scrie mai elegant așa (nu l-am compilat, probabil trebuie ajustat): 

int comun( int  x, int  y ) { //returneaza 1 daca au cifre comune, 0 daca nu au
    int c, retval = 0;
    for ( c = 0; c <= 9; c++ )
        vfc[c] = 0;
    do {
        vfc[x % 10] = 1;
        x /= 10;
    } while ( x > 0 );
    do {
        if ( vcf[y % 10] == 1 )
            vcf[y % 10] = retval = 2;
        y /= 10;
    } while ( y > 0 );
    return retval;
}
  • Mușat: Felicitări, ești printre puținii care au trecut toate testele! Codul arată organizat, la prima vedere. La a doua vedere sînt neglijențe. De exemplu, un vector de frecvență se numește aparitii[], altul frecv[]. Calculul vectorilor de frecvență neglijent, dacă numărul este zero totuși mai intri și în while. Dacă foloseai do ... while ieșea mai elegant. Calculul vectorului comune[] putea fi simplificat, fiecare element este produsul elementelor respective din vectorii de frecvență. Ai ceva repetiții de cod, teste complicate, ajustări de cazuri particulare, dar per total l-ai organizat suficient de bine să-l scoți la capăt, bravo!
  • Nicu: Ai avertismente. Greșeală de gîgă. Ai declarat toate variabilele de tip long long. Groaznic. În rest, ce să zic? Cod care are sens, dar stufos, cu multe repetiții, stegulețe. Genul de cod care este destinat să nu funcționeze pentru că va pierde cazuri particulare.
  • Petcu: În primul rînd felicitări, ai reușit să treci toate testele! Acum, programul este lung și repetitiv, nu am timp să îl înțeleg. Ai multe cazuri, par tratate organizat, dar și multă repetiție de cod. Încă nu recunoști și nu știi să scrii corect o căutare liniară. Preferi să "dai cu forul" ca toți beoțienii. Îți voi da doar niște exemple de cod neelegant. În loc de:
  if( a == 0 )
    vfa[0] = 1;
  while( a > 0 ) {
    vfa[a%10] = 1;
    a /= 10;
  }

puteai cel puțin să pui un else înainte de while. Dar și mai bine era să scrii așa: 

  do {
    vfa[a%10] = 1;
    a /= 10;
  } while( a > 0 );

Un alt exemplu: 

int pot_unifica( long long a, long long b ) {
  int i, g;
  actualizare_vf( a, b );
  g = 0;
  for( i = 0; i < 10; i++ )
    if( vfa[i] > 0 && vfb[i] > 0 )
      g = 1;
  if( g == 0 )
    return 1;
  return 0;
}

În primul rînd ai return înainte de finalul funcției, adică nestructurare. Pentru aceasta îți poți pierde calificarea la IQ Academy. În al doilea rînd returnezi 0 pentru adevărat și 1 pentru fals. Pe dos față de cum este normal. Mai departe, aici avem o căutare liniară tipică. Cu toate acestea ai scris un mare for cu un steguleț. Codul pe care îl știm încă din clasa a cincea ar fi fost: 

int pot_unifica( long long a, long long b ) {
  int i;
  actualizare_vf( a, b );
  i = 0;
  while ( i < 10 && (vfa[i] == 0 || vfb[i] == 0) )
    i++;
  return (i < 10);
}

Funcția se scurtează, devine mai clară și mai eficientă. Atenție la modul de gîndire și de programare, te rog!

  • Petrescu: o soluție mai bună ca a multor colegi ai tăi. Este închegată, nu repetă mult cod, folosește funcții bine. Testele sînt acum descărcabile, poți să o depanezi.
  • Ștefănescu: Atenție! Ai avertisment periculos de compilare, variabila 'rez' nu este inițializată în toate cazurile! Felicitări, ai scris un cod monstru! :-) Mi-e greu să îl înțeleg în timpul limitat pe care îl am. Dar văd că ai multe, multe cazuri particulare. Problema are ea destule cazuri. Tu ai mai introdus în plus. E genul de cod care e destinat să nu funcționeze corect pe toate cazurile.
  • Teodorescu: Cod rezonabil, foarte stufos, cu multe repetiții. Probabil de aceea ratezi anumite cazuri particulare.

Maxarea

Problema maxarea a fost dată la Shumen 2015 juniori. Este o problemă clasică. Ea cere să se determine dreptunghiul de arie maximă într-un skyline, unde un skyline este o înșiruire de blocuri de lățime unu și diverse înălțimi.

Comentarii generale

  • Majoritatea ați scris, în turmă, o rezolvare bazată pe maxp. În ciuda faptului că am discutat care este rezolvarea în lecție. Ce înseamnă acest lucru:
    • Eu vorbesc, eu ascult. Atenția voastră este nihil.
    • Sînteti copiști excepționali. Nu gîndiți, ci transcrieți soluții existente.
  • V-am indicat să citiți numerele cu fgetc() pentru viteză. Cu ocazia aceasta am constatat că:
    • Mulți ați ignorat indicația.
    • Alții s-au descurcat dar atît. Codul este ineficient, nerobust, periculos la olimpiadă. Un simplu spațiu în plus sau un \n lipsă la final de linie vă aruncă codul pe cîmpii. Nedemn de IQ Academy.
    • Puțini au scris cod eficient și robust.
  • Unii din voi nu au înțeles analiza amortizată, ați scris cod pătratic. Am generat un test maximal pe care îl picați cu brio.

Comentarii individuale

  • Benescu: ai cod aproape identic cu al lui Ștefănescu, pînă și denumirea greșită a vectorilor (st[] și stanga[]). Ce se întîmplă? Comentariile sînt aceleași, idee bună, similar cu maxp. Ambii vectori denumiți stînga, deși unul este dreapta. Se poate mai eficient, vezi soluția de mai jos. Nu ai citit întregii cu fgetc().
  • Burac: Citirea cu fgetc() este ineficientă și nerobustă. Idee bună, similar cu maxp. Se poate mai eficient, vezi soluția de mai jos.
  • Calotă: Mulțumesc pentru comentarii. Bravo, parsing corect! Idee bună, similar cu maxp. Se poate mai eficient, vezi soluția de mai jos. Felicitări, nu ai folosit funcții pentru a nu repeta cod.
  • Chivu: programul tău nu folosește nici stivă, nici analiză amortizată. Este pătratic. Nu ai înțeles analiza amortizată, revezi lecția sau pune întrebări.
  • Dimulescu: Mulțumesc pentru comentarii, ajută! Idee de program foarte bună! Se poate mai eficient, vezi soluția de mai jos. Motivul pentru care nu iei 100p este că la final tratezi coloanele de la 0 la n+1. Trebuia să le iei doar pe cele reale, nu și santinelele, adică de la 1 la n. Citirea cu fgetc() este ineficientă și nerobustă.
  • Fares: ai avertisment serios de compilare. Ignori cu beatitudine (ce o fi aia?). Idee bună, similar cu maxp. Se poate mai eficient, vezi soluția de mai jos.
  • Iordache: Citirea cu fgetc() este ineficientă și nerobustă. Ideea algoritmului este bună. Complexitatea nu este rea, dar nici optimală, este O(n·D). Va ieși din timp pe teste maximale (care nu există în problemă).
  • Marcu: Citirea cu fgetc() este ineficientă și nerobustă. Ideea algoritmului este bună. Complexitatea nu este rea, dar nici optimală, este O(n·D). Va ieși din timp pe teste maximale (care nu există în problemă).
  • Mușat: Idee bună, similar cu maxp. Se poate mai eficient, vezi soluția de mai jos. Nu ai citit întregii cu fgetc(). Ai două funcții aproape identice.
  • Nicu: Idee bună, similar cu maxp. Se poate mai eficient, vezi soluția de mai jos. Nu ai citit întregii cu fgetc().
  • Petcu: este a treia oară cînd copiezi (cel puțin cînd te prind eu). Ți-ai pierdut calificarea la IQ Academy. Începînd cu această lecție. Poți reveni dacă vei continua să îți faci lecțiile și să participi la concursuri cu rezultate bune și necopiate.
  • Petrescu: program bun, bravo! O obiecție importantă: nrstiva este folosit într-un mod greu de citit și foarte periculos. Pe de o parte este global. Pe de altă parte îl transmiți ca parametru unei funcții, unde se copiază în nrs. Iar funcția le folosește pe ambele! Crezi că este bine? Minimal, ar trebui să nu pasezi nrstiva ca parametru, să declari nrs local, în funcție, unde îl atribui explicit la valoarea lui nrstiva și apoi îl folosești. Nu ai citit întregii cu fgetc().
  • Ștefănescu: ai cod aproape identic cu al lui Benescu, pînă și denumirea greșită a vectorilor (st[] și stanga[]). Ce se întîmplă? Comentariile sînt aceleași, idee bună, similar cu maxp. Ambii vectori denumiți stînga, deși unul este dreapta. Se poate mai eficient, vezi soluția de mai jos. Nu ai citit întregii cu fgetc().
  • Teodorescu: Citirea cu fgetc() este ineficientă și nerobustă. Nu ai comentarii, mi-e greu să înțeleg ce faci. Dar pot să îți spun că programul tău este pătratic, nu liniar (deci incorect), după felul cum stiva doar crește, nedescrescînd niciodată. Pe un test maximal ar pica la timp.

Tema opțională - rezolvări

Skyline

Problema skyline este o problemă clasică. Cere să se găsească dreptunghiul de arie maximă într-un skyline, unde un skyline este linia lăsata de zgîrie-nori. Cu alte cuvinte o secvență de dreptunghiuri aliniate cu axa Ox. Ea este foarte asemănătoare cu problema maxarea, cu diferența că dreptunghiurile pot avea o lățime mai mare de unu.

Dreptunghi 1

Problema dreptunghi 1

Rezolvări aici [1]

Lecție - permutări, proprietăți

<html5media height="720" width="1280">https://www.algopedia.ro/video/2019-2020/2019-12-05-clasa-7-lectie-info-13-720p.mp4</html5media>

Permutări

O permutare poate fi văzută ca o funcție de rearanjare a valorilor inițiale. Astfel, dacă permutarea noastră este 

2 5 4 3 1

aceasta înseamnă că la o aplicare a permutării pe prima poziție vom avea al doilea element din șirul nepermutat, pe a doua poziție vom avea al cincilea element din șirul original și așa mai departe.

Deci, a aplica o permutare unor obiecte înseamnă a le schimba ordinea conform permutării. Fiecare număr din permutare semnifică poziţia care se va afla în final pe acea poziţie. De exemplu, dacă permutarea este (2 5 4 3 1) și o aplicăm obiectelor (1 2 3 4 5), după prima aplicare obținem chiar permutarea, (2 5 4 3 1), deoarece pe poziţia 1 va veni numărul de pe poziţia 2, pe pozitia 2 va veni numărul de pe poziţia 5 şi aşa mai departe. După a doua aplicare obținem (5 1 3 4 2), după a treia (1 2 4 3 5) și așa mai departe: 

1 2 3 4 5
2 5 4 3 1
5 1 3 4 2
1 2 4 3 5
...

Cum stocăm o permutare? Dacă dorim să o aplicăm unui vector, o putem stoca într-un alt vector, cu mențiunea că, deoarece vectorii încep de la zero, pentru ușurința codului este preferabil să stocăm numerele din permutare minus unu.

Cicluri ale permutărilor

Ne putem pune, în mod natural, o întrebare: dacă pornim cu permutarea identică și aplicăm permutarea noastră în mod repetat, vom ajunge din nou la permutarea identică?

Pentru a răspunde la această întrebare să studiem structura permutărilor. Dacă urmărim felul în care valorile își schimbă locurile vom observa că orice permutare conține cicluri, adică submulțimi ale mulțimii de valori care își schimbă circular valorile între ele. Ciclurile sînt disjuncte. Exemplu: fie permutarea de mai sus (2 5 4 3 1). Pornim cu poziția 1, unde p[1] este 2. Avansăm pe poziția 2, unde p[2] este 5. Avansăm pe poziția 5, unde p[5] = 1, revenind astfel pe poziția 1. Am detectat astfel primul ciclu al permutării, format din (2, 5, 1). Continuăm cu primul element care nu face parte din ciclul găsit, care se află pe poziția 3. p[3] este 4, avansăm pe poziția 4. p[4] este 3, care încheie ciclul. Astfel, permutarea noastră se descompune în două cicluri disjuncte, (2, 5, 1) și (4, 3). Cum putem folosi această proprietate? Iată două exemple:

Exemplul 1

Să se spună dacă un vector de n elemente conține toate numerele de la 1 la n. Memoria suplimentară disponibilă este O(1). Avem voie să modificăm vectorul original.

O soluție bazată pe ciclurile permutărilor este să parcurgem aceste cicluri și să facem elementele 0 pe măsură ce le parcurgem. Dacă vectorul conține o permutare a numerelor 1-n atunci fiecare ciclu trebuie să se încheie acolo unde a început. Dacă parcurgînd ciclurile vectorului ajungem pe o poziție marcată cu 0 dar diferită de începutul ciclului înseamnă că nu avem o permutare. Ciclurile le parcurgem astfel: pornim cu primul element și parcurgem elementele pînă ne întoarcem. Apoi căutăm primul element diferit de 0 și reluăm. Ne oprim fie cînd găsim un ciclu incorect (caz în care nu avem o permutare), fie cînd ieșim din vector (caz în care permutarea este corectă).

Exemplul 2

Dată o permutare, după cîte aplicări obținem din nou permutarea inițială?

Observăm că la fiecare aplicare a permutării ciclurile se rotesc cu 1. Fiecare ciclu i va reveni la poziția inițială după un număr li, care este lungimea ciclului. De aceea va fi nevoie de cmmmc(li) pentru ca toate ciclurile să ajungă în poziția inițială.

Numerotarea permutărilor

Să considerăm permutările a n elemente, în ordine lexicografică. Ele capătă astfel un număr de ordine, prima permutare fiind numărul zero. Ne propunem să facem conversii între numărul de ordine și permutarea asociată.

Baza factorial

Să luăm ca exemplu baza trei. La adunarea cu unu, o cifră pe poziția k se va mări cu unu atunci cînd cifra de pe poziția k-1 trece din 2 în 0. Astfel: 

101222 + 1 =
102000

Cîte numere putem reprezenta în baza trei pe șase cifre? Deoarece fiecare cifră poate avea trei valori vom avea 36 numere posibile.

Aici ne vine ideea: noi ne-am dori ca pe 6 cifre să avem 6! numere reprezentabile. E destul de clar că dacă pentru cifra cea mai din dreapta avem o valoare posibilă, pentru următoarea cifră două valori, pentru următoarea trei, și așa mai departe, numărul de posibilități va fi 6·5·4·3·2·1, adică 6!

Deci, la fel cum reprezentăm numerele în baza trei, zece, sau doi, putem reprezenta numerele într-o bază variabilă, ce crește dinspre dreapta spre stînga. Vom denumi aceasta reprezentarea în baza factorial. Astfel, fiecare cifră este într-o bază diferită! Cifra k (dinspre dreapta spre stînga) se va reprezenta în baza k!.

Iată un exemplu, pe patru cifre, echivalent permutărilor de 4 elemente: 

baza: 4321

   0: 0000
   1: 0010
   2: 0100
   3: 0110
   4: 0200
   5: 0210
   6: 1000
   7: 1010
   8: 1100
   9: 1110
  10: 1200
  11: 1210
  12: 2000
  13: 2010
  14: 2100
  15: 2110
  16: 2200
  17: 2210
  18: 3000
  19: 3010
  20: 3100
  21: 3110
  22: 3200
  23: 3210

Observații:

  • Baza crește de la dreapta către stînga.
  • Valorile cifrelor sînt între zero și baza minus unu.
  • Ultima cifră este mereu zero, nu este o greșeală!
  • Numărul de numere reprezentabile pe n cifre este n!.
  • Numărul de permutări de n elemente este n!.
  • Sperăm, deci, să putem stabili o corespondență unu la unu între aceste numere și mulțimea permutărilor (ea se cheamă bijecție în limbaj matematic).

Pare un pic complicat, dar nu este. Programele de conversie sînt aceleași ca și în baza zece, dar baza va varia de la 1 la n. Iată un exemplu de program care generează toate codurile în baza factorial pe n cifre și le și recompune, pentru exemplificare, la codul în baza zece: 

// Program demonstrativ al bazei factorial
#include <stdio.h>

char nr[11];

int main() {
  int b, n, k, kc, u;

  scanf( "%d", &n ); // n cifre in baza factorial
  u = 1;
  // calculam ultimul numar de ordine (strict mai mare)
  for ( b = 2; b <= n; b++ )
    u *= b;

  k = kc = 0;
  while ( k < u ) {
    // construim numarul nr[] in baza factorial
    kc = k;
    for ( b = 1; b <= n; b++ ) {
      nr[b - 1] = kc % b;
      kc /= b;
    }

    // afisam numarul nr[] in baza factorial
    printf( "%4d: ", k );
    for ( b = n; b > 0; b-- )
      fputc( '0' + nr[b - 1], stdout );

    // recompunem numarul de ordine k din nr[]
    kc = 0;
    for ( b = n; b > 0; b-- )
      kc = kc * b + nr[b - 1];

    printf( " %4d\n", kc );
    
    k++;
  }
  return 0;
}

Ce complexitate au aceste conversii?

Se observă ușor că ele sînt O(n), cîtă vreme n! nu depășește un întreg.

Conversie număr de ordine -> permutare

Problemă: se dă k cuprins între 0 și n!-1, să se afișeze a ka permutare de n în ordine lexicografică.

Soluție: vom calcula numărul k în baza factorial cu n cifre. Apoi, pe baza acestor cifre, vom calcula permutarea.

Exemplu

Să presupunem că ne dorim permutarea de patru elemente cu numărul de ordin 11. Calculînd k obținem 1210. Pentru a obține permutarea vom selecta numerele de la 1 la 4, astfel: 

1210, vom selecta poziția 1 din cele patru cifre, adică numărul 2
1210, vom selecta poziția 2 din cifrele rămase { 1, 3, 4 }, adică 4
1210, vom selecta poziția 1 din cifrele rămase { 1, 3 }, adică 3
1210, vom selecta poziția 0 din cifrele rămase { 1 }, adică 1

Rezultă permutarea 2 4 3 1

Implementare: cea mai simplă implementare este cea în care păstrăm un vector de frecvență al elementelor folosite în permutare, să-i spunem folosit[], similar cu prima metodă de generare a permutărilor, cea mai simplă. Pentru fiecare cifră cf din numărul în baza factorial vom căuta al cf-lea 0 în vectorul de frecvență (al cf-lea număr nefolosit).

Ce complexitate are această implementare?

Pentru fiecare cifră putem parcurge maxim n elemente în vectorul de frecvență. Avem n cifre, deci complexitatea este O(n2) ca timp și O(n) ca memorie.

Iată in exemplu de generare a permutărilor pe baza numărului lor de ordine: 

// Program demonstrativ: generare permutari pe baza numarului lor de ordine
#include <stdio.h>

char nr[10], folosit[10];

int main() {
  int b, n, k, kc, u, i;

  scanf( "%d", &n ); // n cifre in baza factorial
  u = 1;
  // calculam ultimul numar de ordine (strict mai mare)
  for ( b = 2; b <= n; b++ )
    u *= b;

  k = kc = 0;
  while ( k < u ) {
    // construim numarul nr[] in baza factorial
    kc = k;
    for ( b = 1; b <= n; b++ ) {
      nr[b - 1] = kc % b;
      kc /= b;
    }

    // afisam numarul nr[] in baza factorial
    printf( "%4d: ", k );
    for ( b = n; b > 0; b-- )
      fputc( '0' + nr[b - 1], stdout );

    // resetam vectorul de elemente folosite
    for ( b = n - 1; b >= 0; b-- )
      folosit[b] = 0;

    // afisam permutarea
    fputc( ' ', stdout );
    for ( b = n - 1; b >= 0; b-- ) { // parcurgem cifrele nr. in baza factorial
      i = -1;
      while ( nr[b]-- >= 0 )         // sarim peste nr[b]+1 elemente nefolosite
        do
          i++;
        while ( folosit[i] );
      folosit[i] = 1;                // marcam elementul ca folosit
      fputc( '1' + i, stdout );      // si il afisam
    }
    fputc( '\n', stdout );

    k++;
  }
  return 0;
}

Iată ce afișează programul de mai sus pentru n=4: 

   0: 0000 1234
   1: 0010 1243
   2: 0100 1324
   3: 0110 1342
   4: 0200 1423
   5: 0210 1432
   6: 1000 2134
   7: 1010 2143
   8: 1100 2314
   9: 1110 2341
  10: 1200 2413
  11: 1210 2431
  12: 2000 3124
  13: 2010 3142
  14: 2100 3214
  15: 2110 3241
  16: 2200 3412
  17: 2210 3421
  18: 3000 4123
  19: 3010 4132
  20: 3100 4213
  21: 3110 4231
  22: 3200 4312
  23: 3210 4321

Conversie permutare -> număr de ordine

Problemă: se dă o permutare de n. Să se afișeze numărul ei de ordine (în ordine lexicografică), k, cuprins între 0 și n!-1.

Soluție: vom calcula numărul k în baza factorial cu n cifre, pe baza elementelor din permutare.

Exemplu Să presupunem că ne dorim să aflăm numărul de ordine al permutării de 4 elemente: 2 4 3 1. Vom calcula cifrele numărului său de ordine în baza 4!, astfel: 

2 4 3 1, 2 este a doua cifră încă nefolosită, deci prima cifră va fi 1 (2-1)
2 4 3 1, 4 este a treia cifră încă nefolosită din cifrele rămase { 1, 3, 4 }, deci a doua cifră va fi 2 (3-1)
2 4 3 1, 3 este a doua cifră încă nefolosită din cifrele rămase { 1, 3 }, deci a treia cifră va fi 1 (2-1)
2 4 3 1, 1 este prima cifră încă nefolosită din cifrele rămase { 1 }, deci a treia cifră va fi 0 (1-1)

Rezultă numărul în baza factorial: 1210, pe care cînd îl convertim la baza zece avem k=11

La implementare nu vom avea nevoie să memorăm cifrele în baza n!. Pe măsură ce le calculăm vom calcula direct k, numărul de ordine dorit.

Ce complexitate are această implementare?

Pentru fiecare cifră putem parcurge maxim n elemente în vectorul de frecvență. Avem n cifre, deci complexitatea este O(n2) ca timp și O(n) ca memorie.

Iată in exemplu de generare a permutărilor pe baza numărului lor de ordine: 

// Program demonstrativ: calcul numar de ordine pe baza unei permutari
#include <stdio.h>

char nr[10], folosit[10], perm[10];

int main() {
  int b, n, k, kc, u, i, cf;

  scanf( "%d", &n ); // n cifre in baza factorial
  u = 1;
  // calculam ultimul numar de ordine (strict mai mare)
  for ( b = 2; b <= n; b++ )
    u *= b;

  k = kc = 0;
  while ( k < u ) {
    // construim numarul nr[] in baza factorial
    kc = k;
    for ( b = 1; b <= n; b++ ) {
      nr[b - 1] = kc % b;
      kc /= b;
    }

    // afisam numarul nr[] in baza factorial
    printf( "%4d: ", k );
    for ( b = n; b > 0; b-- )
      fputc( '0' + nr[b - 1], stdout );

    // resetam vectorul de elemente folosite
    for ( b = n - 1; b >= 0; b-- )
      folosit[b] = 0;

    // generam permutarea
    fputc( ' ', stdout );
    for ( b = n - 1; b >= 0; b-- ) { // parcurgem cifrele nr. in baza factorial
      i = -1;
      while ( nr[b]-- >= 0 )         // sarim peste nr[b]+1 elemente nefolosite
        do
          i++;
        while ( folosit[i] );
      folosit[i] = 1;                // marcam elementul ca folosit
      fputc( '1' + i, stdout );      // si il afisam
      perm[b] = i;                   // stocam elementul in permutare
    }

    // resetam vectorul de elemente folosite
    for ( b = n - 1; b >= 0; b-- )
      folosit[b] = 0;
    
    // calculam numarul de ordine al permutarii curente
    kc = 0;
    for ( b = n - 1; b >= 0; b-- ) { // parcurgem elementele permutarii
      cf = 0;
      for ( i = perm[b] - 1; i >= 0; i-- ) // pornim in 'folosit[]' in jos
        cf += (1 - folosit[i]);            // cautam cifre nefolosite
      folosit[perm[b]] = 1;                // marcam elementul ca folosit
      kc = kc * (b + 1) + cf; // adaugam cifra curenta la numarul de ordine
    }

    printf( " %4d\n", kc );   // afisam numarul de ordine

    k++;
  }
  return 0;
}

Iată ce afișează programul de mai sus pentru n=4: 

   0: 0000 1234    0
   1: 0010 1243    1
   2: 0100 1324    2
   3: 0110 1342    3
   4: 0200 1423    4
   5: 0210 1432    5
   6: 1000 2134    6
   7: 1010 2143    7
   8: 1100 2314    8
   9: 1110 2341    9
  10: 1200 2413   10
  11: 1210 2431   11
  12: 2000 3124   12
  13: 2010 3142   13
  14: 2100 3214   14
  15: 2110 3241   15
  16: 2200 3412   16
  17: 2210 3421   17
  18: 3000 4123   18
  19: 3010 4132   19
  20: 3100 4213   20
  21: 3110 4231   21
  22: 3200 4312   22
  23: 3210 4321   23

Optimizarea conversiilor

Se pot face cele două conversii mai eficient? Răspunsul wikipedia este că da, ele se pot efectua în O(n log n), dar în practică algoritmii nu sînt folosiți deoarece:

  • n este de obicei prea mic pentru ca diferența între O(n2) și O(n log n) să conteze.
  • De cele mai multe ori cînd avem nevoie de generări de permutări avem situații speciale în care avem algoritmi mai eficienți.

Revenire la problema permutări1

Problema permutări1 a fost dată ca un exercițiu de generare eficientă a permutărilor prin algoritmul cu liste. Ea poate fi rezolvată și altfel: putem citi numerele de ordine ale permutărilor și apoi putem genera și afișa acele permutări.

Cum se compară acest algoritm cu cel original, ce generează toate permutările?

Algoritmul original are complexitate O(n!), deoarece generează toate permutările.

Algoritmul cel nou va genera k permutări. O generare execută O(n2) operații. Complexitatea totală va fi, deci, O(k·n2). Deoarece k este foarte mic (50 000) acest algoritm este mai rapid.

Permutări cu repetiție

Definiție: permutările cu repetiție sînt toate modurile distincte în care putem așeza n obiecte, atunci cînd anumite obiecte sînt identice. De exemplu, permutările șirului 1 1 1 2 2 sînt: 

1 1 1 2 2
1 1 2 1 2
1 1 2 2 1
1 2 1 1 2
1 2 1 2 1
1 2 2 1 1
2 1 1 1 2
2 1 1 2 1
2 1 2 1 1
2 2 1 1 1

Numărul permutărilor cu repetiție este factorialul numărului de obiecte împărțit la factorialele numerelor de obiecte de același tip. De ce? Deoarece pentru fiecare permutare obișnuită, dacă avem t obiecte de același tip, vom avea t! permutări care "arată la fel".

Cum generăm permutări cu repetiție?

Am studiat doi algoritmi de generare de permutări. Ambii pot fi ușor adaptați să genereze permutări cu repetiție.

Algoritmul cu vector de frecvență

Modificarea pentru acest algoritm va fi aceea că un element în vectorul de frecvență va conține numărul de obiecte de acel tip. Atunci cînd așezăm un element în permutare îl scădem din vectorul de frecvență. La revenirea din recursivitate vom aduna unu la vectorul de frecvență, pentru a reveni la valoarea anterioară.

Algoritmul cu listă

Modificarea acestui algoritm constă în faptul că un element al listei va conține o pereche (element, număr de apariții). Cînd parcurgem lista pentru a plasa elemente în permutare, vom scădea unu din numărul de apariții. Dacă numărul de apariții devine zero, vom scoate elementul din listă, readăugîndu-l la loc la revenirea din recursivitate. La revenirea din recursivitate vom aduna unu la numărul de apariții.

Cei doi algoritmi își păstrează complexitățile, în sensul în care cel cu vectori de frecvență generează permutări în O(n) per permutare amortizat, iar cel cu listă are nevoie de O(1) amortizat pentru generarea unei permutări.

Next permutation

Problemă: dată o permutare într-un șir, să se genereze următoarea permutare lexicografică.

Soluție: vom proceda ca la incrementarea unui număr mare. Vom schimba permutarea la coadă, minimal, pentru a o transforma în permutarea următoare. Vom exemplifica algoritmul pe baza next lexicographical permutation algorithm, folosind exemplul (0 1 2 4 3 3 0). Pașii sînt următorii:

Găsirea sufixului descrescător maximal

Pornind de la coadă parcurgem permutarea către stînga cîtă vreme elementele sînt mai mare sau egale. Ne oprim la primul element strict mai mic. În cazul nostru obținem (0 1 2 | 4 3 3 0). În acest moment știm că sufixul este o permutare maximală, nu poate fi mărită decît aducînd elemente dinspre stînga.

Mărirea elementului din stînga sufixului

Deoarece sufixul descrescător nu se mai poate mări, pentru a modifica minimal permutarea va trebui să mărim elementul imediat următor, în cazul nostru 2. Cu ce îl vom înlocui? Cu cel mai mic element strict mai mare ca el, ce se află la dreapta lui. În cazul nostru îl vom înlocui cu 3. Obținem deci prima parte a permutării:

(0 1 3 ... )

Rearanjarea sufixului

În partea din dreapta avem acum elementele din sufix, dintre care dispare un element, cel folosit în prefix, și se adauga primul element din stînga. În cazul nostru au rămas elementele (4 3 0) și elementul 2. Cum formăm cea mai mică permutare lexicografică? Desigur ordonînd crescător elementele rămase. În cazul nostru sufixul va deveni (0 2 3 4). Va rezulta permutarea:

(0 1 3 0 2 3 4)

Optimizarea implementării

Putem scăpa de sortarea elementelor sufixului, la final, deoarece știm că sufixul este descrescător. Putem, deci, să inversăm elementele lui. Înainte de aceasta vom plasa elementul din stînga lui, cel ce a fost mărit. Unde îl plasăm? Astfel încît sufixul original să rămînă descrescător (apoi crescător după inversare), deci la prima poziție dinspre dreapta spre stînga unde vom găsi un element strict mai mare.

Algoritmul final

  1. Caută la coadă sufixul descrescător maximal. El va începe la poziția k.
    1. Dacă k este zero, toată permutarea este descrescătoare, deci ea este ultima, nu mai avem ce genera.
  2. Caută primul element dinspre dreapta care este strict mai mare decît p[k-1].
    1. El va fi la poziția i.
  3. Interschimbă elementele p[k-1] și p[i].
  4. Inversează vectorul p[k..n-1]

Ce complexitate are acest algoritm?

Analiza este la fel ca la algoritmul de generare a permutărilor cu liste: la nivelul k (cu k numerotat crescător de la dreapta la stînga) se fac O(k) calcule. Va rezulta aceeași complexitate amortizată de O(1) per permutarea următoare. Surprinzător, nu?

Temă

Rezolvări aici [2]

Retrieved from "https://www.algopedia.ro/wiki/index.php?title=Clasa_a_VII-a_lecția_13_-_5_dec_2019&oldid=18328"