Clasa a 7-a Lecția 22: Generarea elementelor combinatoriale prin algoritmi de tip succesor: submulțimi, permutări, combinări, aranjamente, next permutation: Difference between revisions
Latest revision as of 14:56, 8 June 2025
Înregistrare video lecție
Permutări
Permutările de N elemente sunt definite ca numărul de moduri de a aranja în șir cele N 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 (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 sunt 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 (ranking / unranking)
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 sunt între zero și baza minus unu.
- Ultima cifră este mereu zero, nu este o greșeală!
- Numărul de numere reprezentabile pe
ncifre esten!. - Numărul de permutări de
nelemente esten!. - 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 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 sunt O(n), câtă vreme n! nu depășește un întreg.
Conversie număr de ordine ➔ permutare (unranking)
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ă un 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 (ranking)
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ă un 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 sunt folosiți deoarece:
neste 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 sunt toate modurile distincte în care putem așeza n obiecte, atunci când anumite obiecte sunt identice. De exemplu, permutările șirului 1 1 1 2 2 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 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ă. Iată cele două implementări:
Permutări cu vector de frecvență
// 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;
}
Permutări cu repetiție cu vector de frecvență
// 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;
}
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ă
// 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;
}
Permutări cu repetiție cu listă
// 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;
}
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 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 (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 adaugă 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?
Combinări
Numim combinări de luate câte și notăm cu submulțimile de elemente dintr-o mulțime de elemente.
Combinări - formulă
Cum le calculăm?
- Știm câte permutări de elemente avem: .
- Primele elemente ale acestor permutări vor constitui o combinare validă.
- Fiecare din prefixele de elemente apare de ori, deoarece prefixul se schimbă doar după ce restul de elemente au fost permutate în toate modurile posibile.
- Deci, numărul de prefixe distincte de elemente este .
- 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 ori. Deci trebuie să împărțim numărul de prefixe la .
- Deci, formula numărului de combinări de luate câte este:
Combinări - formule de recurență
Din formula combinărilor, înlocuind cu și cu , obținem ușor o primă recurență utilă în calculul rapid al unei singure permutări: .
O altă formulă de recurență utilă se obține astfel:
- Avem două variante de a forma combinările de luate câte .
- Prima variantă este să folosim primul element, rămânând să luăm elemente din celelalte . Vom putea, deci, forma combinări.
- A doua variantă este să nu folosim primul element, rămânând să luăm tot elemente, dar din restul de elemente rămase. Vom putea, deci, forma combinări.
- Suma acestor două expresii este chiar numărul de combinări de luate câte :
Combinări - triunghiul lui Pascal
Din ultima recurență obținem o formulă foarte simplă a fiecărei combinări de luat câte , de două combinări de . 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 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 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(N2) ș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 are ca numere coeficienții cu care se înmulțesc numerele din binomul dacă desfacem parantezele. Pentru egal doi sau trei știm formulele de calcul prescurtat, ce implică numerele de pe liniile 2 și 3:
Iată un mod lejer de a obține formula la orice putere 🙂.
Dacă înlocuim și cu 1 în aceste formule obținem o altă formulă:
Suma combinărilor este . Cu alte cuvinte suma numerelor de pe linia n din triunghiul lui Pascal este .
Acest lucru îl știm, însă, de mai demult, de la submulțimi: știm că numărul submulțimilor unei mulțimi este . 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 .
Pe cazul general avem formula combinărilor cu repetiție: .
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
// 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;
}
Combinări cu repetiție
// 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;
}
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
n), 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
n-1), 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
n-2), 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 i să poată fi mărit este să putem adăuga după el k-i elemente. Pentru aceasta pe poziția i putem pune ca element maxim valoarea n - (k - i) = n -k + i. 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.
// 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;
}
Putem demonstra că timpul de generare a următoarei combinări este O(1) amortizat (încercați să demonstrați).
Aranjamente
Numim aranjamente de luate câte și notăm cu modurile de a aranja într-un șir, în ordine, elemente din cele . Ele sunt, de fapt, permutări parțiale, doar de anumite obiecte din cele .
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ă:
Calcul similar cu cel al combinărilor
- Știm câte permutări de elemente avem: .
- Primele elemente ale acestor permutări vor constitui un aranjament valid.
- Fiecare din prefixele de elemente apare de ori, deoarece prefixul se schimbă doar după ce restul de elemente au fost permutate în toate modurile posibile.
- Deci, numărul de prefixe distincte de elemente este .
- Acesta va fi numărul de aranjamente cerut.
Din ambele metode rezultă aceeași formulă:
Proprietăți ale aranjamentelor
- În programare, dacă avem nevoie să calculăm aranjamente vom folosi formula . 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 .
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 NerdArena):
- NNr dată la interviu de inginer software la Google Inc
- Permutari1 ca aplicație la unranking
- Sport dată la ONI 2011 clasa a 8a
Tema opțională
Să se rezolve următoarele probleme (program C trimis la NerdArena):
- Taburet dată la ONI 2011 baraj gimnaziu, ca aplicație a permutărilor descrise ca funcție (rotațiile taburetelor)
- 2 Numere dată la ONI 2008 baraj gimnaziu, ca aplicație a next_permutation
- Aranjamente ca aplicație la generarea eficientă de aranjamente
