View source for Clasa a 7-a Lecția 22: Generarea elementelor combinatoriale prin algoritmi de tip succesor: submulțimi, permutări, combinări, aranjamente, next permutation

== Înregistrare video lecție ==

<youtube height="720" width="1280">https://youtu.be/CVOXXa6i8fs</youtube>


== Permutări ==

Permutările de <source lang="C" enclose="none">N</source> elemente sunt definite ca numărul de moduri de a aranja în șir cele <source lang="C" enclose="none">N</source> elemente. Cred că formula numărului de permutări distincte este destul de ușor de demonstrat, v-o las ca exercițiu: 

 P(N) = N!


=== Permutările ca funcții de rearanjare ===

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 <tt>(2 5 4 3 1)</tt> și o aplicăm obiectelor <tt>(1 2 3 4 5)</tt>, după prima aplicare obținem chiar permutarea, <tt>(2 5 4 3 1)</tt>, 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 <tt>(5 1 3 4 2)</tt>, după a treia <tt>(1 2 4 3 5)</tt> și așa mai departe:

<pre>
1 2 3 4 5
2 5 4 3 1
5 1 3 4 2
1 2 4 3 5
...
</pre>

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 sunt disjuncte. 

Exemplu: fie permutarea de mai sus <tt>(2 5 4 3 1)</tt>. Pornim cu poziția 1, unde <source lang="C" enclose="none">p[1]</source> este 2. Avansăm pe poziția 2, unde <source lang="C" enclose="none">p[2]</source> este 5. Avansăm pe poziția 5, unde <source lang="C" enclose="none">p[5] = 1</source>, revenind astfel pe poziția 1. Am detectat astfel primul ciclu al permutării, format din <tt>(2, 5, 1)</tt>. Continuăm cu primul element care nu face parte din ciclul găsit, care se află pe poziția 3. <source lang="C" enclose="none">p[3]</source> este 4, avansăm pe poziția 4. <source lang="C" enclose="none">p[4]</source> este 3, care încheie ciclul. Astfel, permutarea noastră se descompune în două cicluri disjuncte, <tt>(2, 5, 1)</tt> și <tt>(4, 3)</tt>. 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 <source lang="C" enclose="none">n</source>. 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 <source lang="C" enclose="none">1-n</source> 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 <source lang="C" enclose="none">i</source> va reveni la poziția inițială după un număr <code>l<sub>i</sub></code>, care este lungimea ciclului. De aceea va fi nevoie de <code>cmmmc(l<sub>i</sub>)</code> pentru ca toate ciclurile să ajungă în poziția inițială.


=== Numerotarea permutărilor (ranking / unranking) ===

Să considerăm permutările a <source lang="C" enclose="none">n</source> 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 <source lang="C" enclose="none">k</source> se va mări cu unu atunci când cifra de pe poziția <source lang="C" enclose="none">k-1</source> 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 <tt>6!</tt> 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 <tt>6·5·4·3·2·1</tt>, adică <tt>6!</tt>.

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 <source lang="C" enclose="none">k</source> (dinspre dreapta spre stânga) se va reprezenta în baza <source lang="C" enclose="none">k!</source>.

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 sunt între zero și baza minus unu.
* Ultima cifră este mereu zero, nu este o greșeală!
* Numărul de numere reprezentabile pe <source lang="C" enclose="none">n</source> cifre este <source lang="C" enclose="none">n!</source>.
* Numărul de permutări de <source lang="C" enclose="none">n</source> elemente este <source lang="C" enclose="none">n!</source>.
* 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 sunt aceleași ca și în baza zece, dar baza va varia de la 1 la <source lang="C" enclose="none">n</source>. Iată un exemplu de program care generează toate codurile în baza factorial pe <source lang="C" enclose="none">n</source> cifre și le și recompune, pentru exemplificare, la codul în baza zece:

<syntaxhighlight lang="c" line>
// 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;
}
</syntaxhighlight>


Ce complexitate au aceste conversii?

Se observă ușor că ele sunt ''O(n)'', câtă vreme <source lang="C" enclose="none">n!</source> nu depășește un întreg.


==== Conversie număr de ordine ➔ permutare (unranking) ====

'''Problemă:''' se dă <source lang="C" enclose="none">k</source> cuprins între 0 și <source lang="C" enclose="none">n! - 1</source>, să se afișeze a <code>k<sup>a</sup></code> permutare de <source lang="C" enclose="none">n</source> în ordine lexicografică.


'''Soluție:''' vom calcula numărul <source lang="C" enclose="none">k</source> în baza factorial cu <source lang="C" enclose="none">n</source> 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 <source lang="C" enclose="none">k</source> obținem <tt>1210</tt>. 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 <tt>2 4 3 1</tt>.


'''Implementare:''' cea mai simplă implementare este cea în care păstrăm un vector de frecvență al elementelor folosite în permutare, să-i spunem <source lang="C" enclose="none">folosit[]</source>, 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 <source lang="C" enclose="none">cf</source>-lea 0 în vectorul de frecvență (al <source lang="C" enclose="none">cf</source>-lea număr nefolosit).


Ce complexitate are această implementare?

Pentru fiecare cifră putem parcurge maxim <source lang="C" enclose="none">n</source> elemente în vectorul de frecvență. Avem <source lang="C" enclose="none">n</source> cifre, deci complexitatea este ''O(n<sup>2</sup>)'' ca timp și ''O(n)'' ca memorie.

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

<syntaxhighlight lang="c" line>
// 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;
}
</syntaxhighlight>


Iată ce afișează programul de mai sus pentru <source lang="C" enclose="none">n = 4</source>:

   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 (ranking) ====

'''Problemă:''' se dă o permutare de <source lang="C" enclose="none">n</source>. Să se afișeze numărul ei de ordine (în ordine lexicografică), <source lang="C" enclose="none">k</source>, cuprins între 0 și <source lang="C" enclose="none">n! - 1</source>.

'''Soluție:''' vom calcula numărul <source lang="C" enclose="none">k</source> în baza factorial cu <source lang="C" enclose="none">n</source> 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: <tt>2 4 3 1</tt>. Vom calcula cifrele numărului său de ordine în baza <tt>4!</tt>, 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: <tt>1210</tt>, pe care când îl convertim la baza zece avem <source lang="C" enclose="none">k = 11</source>.

La implementare nu vom avea nevoie să memorăm cifrele în baza <source lang="C" enclose="none">n!</source>. Pe măsură ce le calculăm vom calcula direct <source lang="C" enclose="none">k</source>, numărul de ordine dorit.


Ce complexitate are această implementare?

Pentru fiecare cifră putem parcurge maxim <source lang="C" enclose="none">n</source> elemente în vectorul de frecvență. Avem <source lang="C" enclose="none">n</source> cifre, deci complexitatea este ''O(n<sup>2</sup>)'' ca timp și ''O(n)'' ca memorie.

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

<syntaxhighlight lang="c" line>
// 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;
}
</syntaxhighlight>


Iată ce afișează programul de mai sus pentru <source lang="C" enclose="none">n = 4</source>:

   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 [https://en.wikipedia.org/wiki/Permutation#Algorithms_to_generate_permutations wikipedia] este că da, ele se pot efectua în ''O(n log n)'', dar în practică algoritmii nu sunt folosiți deoarece:

* <source lang="C" enclose="none">n</source> este de obicei prea mic pentru ca diferența între ''O(n<sup>2</sup>)'' ș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 [https://www.nerdarena.ro/problema/permutari1 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 <source lang="C" enclose="none">k</source> permutări. O generare execută ''O(n<sup>2</sup>)'' operații. Complexitatea totală va fi, deci, ''O(k·n<sup>2</sup>)''. Deoarece <source lang="C" enclose="none">k</source> este foarte mic (50 000) acest algoritm este mai rapid.


=== Permutări cu repetiție ===

Definiție: permutările cu repetiție sunt toate modurile distincte în care putem așeza <source lang="C" enclose="none">n</source> obiecte, atunci când anumite obiecte sunt identice. De exemplu, permutările șirului <tt>1 1 1 2 2</tt> sunt:

 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 <source lang="C" enclose="none">t!</source> 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ă. Iată cele două implementări:


===== Permutări cu vector de frecvență =====

<syntaxhighlight lang="c" line>
// Generare permutari prin recursivitate (pseudo backtracking)
// Permutari in O(n) cu vector de frecventa
#include <stdio.h>

char folosit[10], sol[10];
FILE *fin, *fout;

void perm( int n, int poz ) {
  int i;

  if ( poz == n ) {           // daca am umplut n pozitii
    for ( i = 0; i < n; i++ ) // afiseaza combinarea curenta
      fprintf( fout, "%d ", (int)sol[i] );
    fprintf( fout, "\n" );
  } else
    for ( sol[poz] = 1; sol[poz] <= n; sol[poz]++ )
      if ( !folosit[(int)sol[poz]] ) { // daca elementul curent nu e folosit
        folosit[(int)sol[poz]] = 1;    // marcheaza-l ca folosit
        perm( n, poz + 1 );            // genereaza restul permutarii
        folosit[(int)sol[poz]] = 0;    // demarcheaza elementul
      }
}

int main() {
  int n;

  fin = fopen( "perm.in", "r" );
  fscanf( fin, "%d", &n );
  fclose( fin );

  fout = fopen( "perm.out", "w" );
  perm( n, 0 ); // genereaza permutari de n, pornind in solutie de la poz 0
  fclose( fout );

  return 0;
}
</syntaxhighlight>


===== Permutări cu repetiție cu vector de frecvență =====

<syntaxhighlight lang="c" line>
// Generare permutari cu repetitie prin recursivitate (pseudo backtracking)
// Permutari in O(n) cu vector de frecventa
#include <stdio.h>

char nrel[15], sol[15];
FILE *fin, *fout;

void perm( int n, int poz ) {
  int i;

  if ( poz == n ) {           // daca am umplut n pozitii
    for ( i = 0; i < n; i++ ) // afiseaza combinarea curenta
      fprintf( fout, "%d ", (int)sol[i] );
    fprintf( fout, "\n" );
  } else
    for ( sol[poz] = 1; sol[poz] <= n; sol[poz]++ )
      if ( nrel[(int)sol[poz]] ) { // daca mai avem elemente sol[poz]
        nrel[(int)sol[poz]]--;     // marcheaza-l ca folosit
        perm( n, poz + 1 );        // genereaza restul permutarii
        nrel[(int)sol[poz]]++;     // adauga elementul la loc
      }
}

int main() {
  int n, i, e;

  fin = fopen( "perm.in", "r" );
  fscanf( fin, "%d", &n );
  for ( i = 0; i < n; i++ ) {
    fscanf( fin, "%d", &e );
    nrel[e]++;
  }
  fclose( fin );

  fout = fopen( "perm.out", "w" );
  perm( n, 0 ); // genereaza permutari de n, pornind in solutie de la poz 0
  fclose( fout );

  return 0;
}
</syntaxhighlight>


==== 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. Iată cele două implementări:

===== Permutări cu listă =====

<syntaxhighlight lang="c" line>
// Generare permutari prin recursivitate (pseudo backtracking)
// Permutari in O(1) cu lista
#include <stdio.h>

#define NIL -1
#define MAXN 10

char next[MAXN + 1], // lista de numere 1..n
  sol[MAXN];         // contine permutarea curenta
FILE *fin, *fout;

void perm( int n, int poz ) {
  int i;

  if ( poz == n ) {
    for ( i = 0; i < n; i++ ) // afiseaza permutarea curenta
      fprintf( fout, "%d ", (int)sol[i] );
    fprintf( fout, "\n" );
  } else {
    i = 0; // pointer la elementul din-naintea elementului curent
    while ( next[i] != NIL ) { // pentru fiecare element din lista
      sol[poz] = next[i];      // il plasam in vectorul solutie
      next[i] = next[(int)next[i]]; // il eliminam din lista
      perm( n, poz + 1 );      // reapelam cu pozitia urmatoare
      i = next[i] = sol[poz];  // refacem legatura si avansam i in lista
    }
  }
}

int main() {
  int n, i;

  fin = fopen( "perm.in", "r" );
  fscanf( fin, "%d", &n );
  fclose( fin );

  // initializare lista numere
  for ( i = 0; i < n; i++ )
    next[i] = i + 1;
  next[n] = NIL;

  fout = fopen( "perm.out", "w" );
  perm( n, 0 ); // genereaza permutari de n, pornind in solutie de la poz 0
  fclose( fout );

  return 0;
}
</syntaxhighlight>


===== Permutări cu repetiție cu listă =====

<syntaxhighlight lang="c" line>
// Generare permutari cu repetitie prin recursivitate (pseudo backtracking)
// Permutari in O(1) cu lista
#include <stdio.h>

#define NIL -1
#define MAXN 15

char nrel[MAXN + 1], next[MAXN + 1], // lista de numere 1..k
  sol[MAXN];                         // contine permutarea curenta
FILE *fin, *fout;

void perm( int n, int poz ) {
  int i;

  if ( poz == n ) {
    for ( i = 0; i < n; i++ ) // afiseaza permutarea curenta
      fprintf( fout, "%d ", (int)sol[i] );
    fprintf( fout, "\n" );
  } else {
    i = 0; // pointer la elementul din-naintea elementului curent
    while ( next[i] != NIL ) {  // pentru fiecare element din lista
      sol[poz] = next[i];       // il plasam in vectorul solutie
      if ( --nrel[(int)next[i]] == 0 ) { // mai avem elemente tip next[i]?
        next[i] = next[(int)next[i]];    // il eliminam din lista
        perm( n, poz + 1 ); // reapelam cu pozitia urmatoare
        next[i] = sol[poz]; // refacem legatura
      } else
        perm( n, poz + 1 ); // reapelam cu pozitia urmatoare fara sa eliminam

      nrel[(int)next[i]]++; // adaugam la loc elementul
      i = next[i]; // avansam i in lista de elemente
    }
  }
}

int main() {
  int n, i, e;

  fin = fopen( "perm.in", "r" );
  fscanf( fin, "%d", &n );
  for ( i = 0; i < n; i++ ) {
    fscanf( fin, "%d", &e );
    nrel[e]++;
  }
  fclose( fin );

  // initializare lista numere
  i = next[0] = 1;
  while ( nrel[i] ) {
    next[i] = i + 1;
    i++;
  }
  next[i - 1] = NIL; // marcam finalul de lista

  fout = fopen( "perm.out", "w" );
  perm( n, 0 ); // genereaza permutari de n, pornind in solutie de la poz 0
  fclose( fout );

  return 0;
}
</syntaxhighlight>


=== 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 [https://www.nayuki.io/page/next-lexicographical-permutation-algorithm next lexicographical permutation algorithm], folosind exemplul <tt>(0 1 2 4 3 3 0)</tt>. Pașii sunt următorii:


==== Găsirea sufixului descrescător maximal ====

Pornind de la coadă parcurgem permutarea către stânga câtă vreme elementele sunt mai mare sau egale. Ne oprim la primul element strict mai mic. În cazul nostru obținem <tt>(0 1 2 | 4 3 3 0)</tt>. Î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 adaugă primul element din stânga. În cazul nostru au rămas elementele <tt>(4 3 0)</tt> ș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 <tt>(0 2 3 4)</tt>. 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 ====

<pre>
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]
</pre>


Ce complexitate are acest algoritm?

Analiza este la fel ca la algoritmul de generare a permutărilor cu liste: la nivelul <source lang="C" enclose="none">k</source> (cu <source lang="C" enclose="none">k</source> 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?


== Combinări ==

Numim combinări de <math>N</math> luate câte <math>K</math> și notăm cu <math>C_N^K</math> submulțimile de <math>K</math> elemente dintr-o mulțime de <math>N</math> elemente.


=== Combinări - formulă ===

Cum le calculăm?

* Știm câte permutări de <math>N</math> elemente avem: <math>N!</math>.
* Primele <math>K</math> elemente ale acestor permutări vor constitui o combinare validă.
* Fiecare din prefixele de <math>K</math> elemente apare de <math>(N - K)!</math> ori, deoarece prefixul se schimbă doar după ce restul de <math>N - K</math> elemente au fost permutate în toate modurile posibile.
* Deci, numărul de prefixe distincte de <math>K</math> elemente este <math>\frac{N!}{(N-K)!}</math>.
* Prefixele au o ordine, spre deosebire de permutări. Vrem să luăm în considerare numai prefixele ordonate crescător.
* De câte ori apare un prefix ordonat crescător dar în altă permutare? De <math>K!</math> ori. Deci trebuie să împărțim numărul de prefixe la <math>K!</math>.
* Deci, formula numărului de combinări de <math>N</math> luate câte <math>K</math> este: <math>C_N^K = \frac{N!}{K! \cdot (N-K)!}</math>


=== Combinări - formule de recurență ===

Din formula combinărilor, înlocuind <math>N</math> cu <math>N-1</math> și <math>K</math> cu <math>K-1</math>, obținem ușor o primă recurență utilă în calculul rapid al unei singure permutări: <math>C_N^K = 
 \frac{N}{K} \cdot C_{N-1}^{K-1}</math>.

O altă formulă de recurență utilă se obține astfel:

# Avem două variante de a forma combinările de <math>N</math> luate câte <math>K</math>.
# Prima variantă este să folosim primul element, rămânând să luăm <math>K-1</math> elemente din celelalte <math>N-1</math>. Vom putea, deci, forma <math>C_{N-1}^{K-1}</math> combinări.
# A doua variantă este să nu folosim primul element, rămânând să luăm tot <math>K</math> elemente, dar din restul de <math>N-1</math> elemente rămase. Vom putea, deci, forma <math>C_{N-1}^{K}</math> combinări.
# Suma acestor două expresii este chiar numărul de combinări de <math>N</math> luate câte <math>K</math>: <math>C_N^K = C_{N-1}^{K-1} + C_{N-1}^K</math>


=== Combinări - triunghiul lui Pascal ===

Din ultima recurență obținem o formulă foarte simplă a fiecărei combinări de <math>N</math> luat câte <math>K</math>, de două combinări de <math>N-1</math>. Ele pot fi aranjate vizual într-un triunghi numit triunghiul lui Pascal:

 0             1
 1           1   1
 2         1   2   1
 3       1   3   3   1
 4     1   4   6   4   1
 5   1   5  10  10   5   1

Combinările de <math>N</math> luate câte zero înseamnă că nu vom lua nici un element. Există o singură astfel de submulțime, mulțimea vidă. De aceea combinările de <math>N</math> luate câte zero sunt 1.

Triunghiul lui Pascal este util atunci când avem multe calcule ce implică diverse combinări. El se poate precalcula în ''O(N<sup>2</sup>)'' și va fi memorat ca o matrice (nu-l vom centra, ca în figură 🙂 ).

Numerele din triunghiul lui Pascal se numesc și coeficienți binomiali deoarece linia <math>N</math> are ca numere coeficienții cu care se înmulțesc numerele din binomul <math>(a + b)^N</math> dacă desfacem parantezele. Pentru <math>N</math> egal doi sau trei știm formulele de calcul prescurtat, ce implică numerele de pe liniile 2 și 3:

<math>(a+b)^2 = a^2 + 2ab + b^2</math>

<math>(a+b)^3 = a^3 + 3a^2b + 3ab^2 + b^3</math>

Iată un mod lejer de a obține formula la orice putere 🙂.

Dacă înlocuim <math>a</math> și <math>b</math> cu 1 în aceste formule obținem o altă formulă: 

<math>(1+1)^n = C_n^0 + C_n^1 +C_n^2 + ... + C_n^n = 2^n</math>

Suma combinărilor este <math>2^n</math>. Cu alte cuvinte suma numerelor de pe linia n din triunghiul lui Pascal este <math>2^n</math>.

Acest lucru îl știm, însă, de mai demult, de la submulțimi: știm că numărul submulțimilor unei mulțimi este <math>2^n</math>. Iar combinările luate în totalitate formează chiar toate submulțimile unei mulțimi.


=== Combinări cu repetiție ===

Combinările cu repetiție sunt similare cu cele obișnuite, doar că putem alege un obiect din mulțime de oricâte ori. De exemplu, combinările cu repetiție a patru obiecte luate câte trei sunt:

 1 1 1 
 1 1 2 
 1 1 3 
 1 1 4 
 1 2 2 
 1 2 3 
 1 2 4 
 1 3 3 
 1 3 4 
 1 4 4 
 2 2 2 
 2 2 3 
 2 2 4 
 2 3 3 
 2 3 4 
 2 4 4 
 3 3 3 
 3 3 4 
 3 4 4 
 4 4 4 


Cum deducem formula pentru combinările cu repetiție?

Să luăm cazul de mai sus. Avem de ales din elementele 1 2 3 și 4, în această ordine, putând lua un element de mai multe ori. Să ne imaginăm că dispunem de trei separatoare pe care la putem plasa oriunde între cele patru numere. Numărul după care plasez un separator este luat. Iată:

 1 1 1    1 | | | 2 3 4
 1 1 2    1 | | 2 | 3 4
 1 1 3    1 | | 2 3 | 4
 1 1 4    1 | | 2 3 4 |
 1 2 2    1 | 2 | | 3 4
 1 2 3    1 | 2 | 3 | 4 
 ...


Dacă avem două separatoare unul după altul ele se referă la același număr.

Este, sper, clar, că în acest fel putem genera toate combinările cu repetiție de 4 luate câte trei. Care este egal cu numărul de moduri în care putem plasa separatoarele. Avem cu totul 6 poziții pe care putem plasa, deoarece poziția 1 nu este validă - nu este după un număr. În rest, orice plasare este bună, deci formula va fi <math>C_6^3</math>.

Pe cazul general avem formula combinărilor cu repetiție: <math>CR_n^k=C_{n+k-1}^k</math>.

Algoritmul de generare a combinărilor cu repetiție este aproape identic cu cel de generare a combinărilor fără repetiție. Diferența este că vom varia elementele începând cu elementul anterior, în loc de elementul anterior plus 1. Iată cele două implementări:


==== Combinări ====

<syntaxhighlight lang="c" line>
// Generare combinari folosind recursivitate (pseudo backtracking)
// O(1) per combinare
#include <stdio.h>

#define MAXN 15

char sol[MAXN + 1]; // santinela pe prima pozitie
FILE *fin, *fout;

void comb( int n, int k, int pos ) {
  int i;

  if ( pos > k ) {
    for ( i = 1; i <= k; i++ )
      fprintf( fout, "%d ", (int)sol[i] );
    fprintf( fout, "\n" );
  } else
    for ( sol[pos] = sol[pos - 1] + 1; sol[pos] <= (n - (k - pos)); sol[pos]++ )
      comb( n, k, pos + 1 );
}

int main() {
  int n, k;

  fin = fopen( "comb.in", "r" );
  fscanf( fin, "%d%d", &n, &k );
  fclose( fin );
  
  sol[0] = 0; // inutil, vreau sa subliniez ca este important

  fout = fopen( "comb.out", "w" );
  comb( n, k, 1 );
  fclose( fout );
  
  return 0;
}
</syntaxhighlight>


==== Combinări cu repetiție ====

<syntaxhighlight lang="c" line>
// Generare combinari cu repetitie folosind recursivitate (pseudo backtracking)
// O(1) per combinare
#include <stdio.h>

#define MAXN 15

char sol[MAXN + 1]; // santinela pe prima pozitie
FILE *fin, *fout;

void comb( int n, int k, int pos ) {
  int i;

  if ( pos > k ) {
    for ( i = 1; i <= k; i++ )
      fprintf( fout, "%d ", (int)sol[i] );
    fprintf( fout, "\n" );
  } else
    for ( sol[pos] = sol[pos - 1]; sol[pos] <= n; sol[pos]++ )
      comb( n, k, pos + 1 );
}

int main() {
  int n, k;

  fin = fopen( "comb.in", "r" );
  fscanf( fin, "%d%d", &n, &k );
  fclose( fin );
  
  sol[0] = 1; // pentru a seta primul element la 1

  fout = fopen( "comb.out", "w" );
  comb( n, k, 1 );
  fclose( fout );
  
  return 0;
}
</syntaxhighlight>


Algoritmul este ușor de analizat, el generând fiecare combinare în ''O(1)'' (excluzând afișarea).


=== Next combination ===

Sper deosebire de next permutation care există în C++ STL, ''next_combination'' nu există. Să-l scriem noi 🙂. Este vorba, desigur, despre generarea următoarei combinări în ordine lexicografică.

Dacă ne gândim puțin nu este prea greu: dată o combinare trebuie să generăm următoarea combinare. Să observăm:

* Dacă putem adăuga 1 la ultimul element (dacă nu este egal cu <source lang="C" enclose="none">n</source>), adăugăm și obținem următoarea combinare.
* În caz contrar, dacă putem adăuga 1 la penultimul element (dacă nu este egal cu <source lang="C" enclose="none">n-1</source>), adăugăm, apoi setăm ultimul element la valoarea acestui element plus unu.
* În caz contrar, dacă putem adăuga 1 la antepenultimul element (dacă nu este egal cu <source lang="C" enclose="none">n-2</source>), adăugăm, apoi setăm următoarele două elemente din 1 în 1.

Cred că observăm regula: vom parcurge combinarea curentă de la coadă spre cap până ce găsim un element ce poate fi mărit. Condiția ca un element pe poziția <source lang="C" enclose="none">i</source> să poată fi mărit este să putem adăuga după el <source lang="C" enclose="none">k-i</source> elemente. Pentru aceasta pe poziția <source lang="C" enclose="none">i</source> putem pune ca element maxim valoarea <source lang="C" enclose="none">n - (k - i) = n -k + i</source>. Pentru ca poziția la care ne vom opri să putem adăuga unu, trebuie ca valoarea ei sa fie strict mai mică.

Iată un program care generează combinările de n luate câte k folosind algoritmul next_combination.

<syntaxhighlight lang="c" line>
// Generare combinari folosind next_combination
// O(1) per combinare
#include <stdio.h>

#define MAXN 24

char sol[MAXN + 1]; // santinela pe prima pozitie

// primeste o combinare in sol si genereaza urmatoarea combinare
// returneaza 0 daca nu mai avem combinari sau 1 in caz de succes
int next_comb( int n, int k ) {
  int i;

  i = k;
  while ( sol[i] == n - k + i )
    i--;

  if ( i > 0 ) { // daca nu am terminat combinarile
    // i este pozitionat pe primul element ce poate fi marit
    // toate elementele de dupa pozitia i vor fi din 1 in 1
    sol[i]++;
    for ( i++; i <= k; i++ )
      sol[i] = sol[i - 1] + 1;
  }

  return i > 0;
}

int main() {
  FILE *fin, *fout;
  int n, k, i;

  fin = fopen( "comb.in", "r" );
  fscanf( fin, "%d%d", &n, &k );
  fclose( fin );

  for ( i = 1; i < k; i++ )
    sol[i] = i;
  
  sol[0] = 0;     // inutil, vreau sa subliniez ca este important
  sol[k] = k - 1; // pentru a genera prima combinare
  
  fout = fopen( "comb.out", "w" );
  while ( next_comb( n, k ) ) {
    for ( i = 1; i <= k; i++ )
      fprintf( fout, "%d ", sol[i] );
    fprintf( fout, "\n" );
  }
  fclose( fout );
  
  return 0;
}
</syntaxhighlight>


Putem demonstra că timpul de generare a următoarei combinări este ''O(1)'' amortizat (încercați să demonstrați).


== Aranjamente ==

Numim aranjamente de <math>n</math> luate câte <math>k</math> și notăm cu <math>A_N^K</math> modurile de a aranja într-un șir, în ordine, <math>k</math> elemente din cele <math>n</math>. Ele sunt, de fapt, permutări parțiale, doar de anumite obiecte din cele <math>n</math>.


=== Aranjamente - formulă ===

Cum le calculăm?

Avem mai multe moduri de a le calcula


=== Permutări de combinări ===

Generăm toate combinările posibile. Pe fiecare din ele o permutăm în toate modurile posibile. În acest fel obținem aranjamente distincte și le obținem pe toate. Rezultă o formulă cunoscută: 

<math>A_N^K=C_N^K \cdot P_K</math>


=== Calcul similar cu cel al combinărilor ===

* Știm câte permutări de <math>N</math> elemente avem: <math>N!</math>.
* Primele <math>K</math> elemente ale acestor permutări vor constitui un aranjament valid.
* Fiecare din prefixele de <math>K</math> elemente apare de <math>(N - K)!</math> ori, deoarece prefixul se schimbă doar după ce restul de <math>N - K</math> elemente au fost permutate în toate modurile posibile.
* Deci, numărul de prefixe distincte de <math>K</math> elemente este <math>\frac{N!}{(N-K)!}</math>.
* Acesta va fi numărul de aranjamente cerut.

Din ambele metode rezultă aceeași formulă:
<math>A_N^K = \frac{N!}{(N-K)!}</math>


=== Proprietăți ale aranjamentelor ===

# În programare, dacă avem nevoie să calculăm aranjamente vom folosi formula <math>A_N^K=C_N^K \cdot P_K</math> . Putem precalcula combinările și permutările.
# Aranjamentele se comportă mai mult ca niște permutări decât ca niște combinări.
# Programul de generare prin funcție recursivă va semăna cu cel de permutări, nu cu cel de combinări.
# Putem aplica o procedură de ''next_arrangement''. Ea va fi o combinație între cea de la permutări cu cea de la combinări.
# Putem aplica procedura de ranking / unranking de la permutări, cu diferența că baza factorial nu pornește de la 1 ci de la <math>n-k</math>.

Puteți încerca să implementați generarea, next_arrangement și ranking/unranking, dacă vreți.


== Tema 22 ==

Să se rezolve următoarele probleme (program C trimis la [https://www.nerdarena.ro/ NerdArena]):

* [https://www.nerdarena.ro/problema/nnr NNr] dată la interviu de inginer software la Google Inc
* [https://www.nerdarena.ro/problema/permutari1 Permutari1] ca aplicație la unranking
* [https://www.nerdarena.ro/problema/sport Sport] dată la ONI 2011 clasa a 8a


== Tema opțională ==

Să se rezolve următoarele probleme (program C trimis la [https://www.nerdarena.ro/ NerdArena]):

* [https://www.nerdarena.ro/problema/taburet Taburet] dată la ONI 2011 baraj gimnaziu, ca aplicație a permutărilor descrise ca funcție (rotațiile taburetelor)
* [https://www.nerdarena.ro/problema/2numere 2 Numere] dată la ONI 2008 baraj gimnaziu, ca aplicație a ''next_permutation''
* [https://www.nerdarena.ro/problema/aranjamente Aranjamente] ca aplicație la generarea eficientă de aranjamente


[http://solpedia.francu.com/wiki/index.php?title=Clasa_a_7-a_Lec%C8%9Bia_22:_Generarea_elementelor_combinatoriale_prin_algoritmi_de_tip_succesor:_submul%C8%9Bimi,permut%C4%83ri,_combin%C4%83ri,_aranjamente,_next_permutation Accesează rezolvarea temei 22]