Programare Competitivă

Algoritmi de tip succesor

Algoritmii de tip succesor generează toate configurațiile unei probleme combinatoriale (submulțimi, produs cartezian, combinări, permutări) iterativ, în ordine lexicografică, fără recursivitate.

Ideea: pornim de la prima configurație (cea mai mică), și la fiecare pas calculăm succesorul - configurația imediat următoare din punct de vedere lexicografic. Când nu mai există succesor, ne oprim.

Ce înseamnă “ordine lexicografică”?

Două configurații reprezentate ca vectori x = (x1, x2, ..., xn) și y = (y1, y2, ..., ym) se compară ca la dicționar:

x precede pe y dacă există k astfel încât xi = yi pentru orice i < k și xk < yk, sau n < m și x e prefix al lui y.

(1, 2, 3) < (1, 2, 4)   // difera la poz 3: 3 < 4
(1, 2)    < (1, 2, 5)   // primul e prefix
(2, 1)    > (1, 9, 9)   // difera la poz 1: 2 > 1

Structura generală a unui algoritm de tip succesor

1. Inițializăm cu prima configurație (cea mai mică lexicografic)
2. Cât timp mai există succesor:
   - Afișăm configurația curentă
   - Generăm succesorul

Pentru a genera succesorul, căutăm cea mai din dreapta poziție care poate fi mărită, o mărim cu 1, și resetăm pozițiile din dreapta ei la valoarea minimă.

1. Produs cartezian

Problema

Fie n și lungimile L = (L[0], L[1], ..., L[n-1]). Generăm toate elementele produsului cartezian:

{1, 2, ..., L[0]} × {1, 2, ..., L[1]} × ... × {1, 2, ..., L[n-1]}

Exemplu

n = 3, L = (2, 3, 2). Avem 2*3*2 = 12 elemente:

(1,1,1), (1,1,2), (1,2,1), (1,2,2), (1,3,1), (1,3,2),
(2,1,1), (2,1,2), (2,2,1), (2,2,2), (2,3,1), (2,3,2)

Algoritmul

  1. Pornim cu E = (1, 1, ..., 1).
  2. Pentru succesor, găsim cea mai din dreapta poziție i cu E[i] < L[i]:
    • Creștem E[i] cu 1
    • Toate pozițiile din dreapta lui i → 1
  3. Dacă nicio poziție nu poate fi mărită, STOP.

Cod

#include <fstream>
using namespace std;
ifstream fin("date.in");
ofstream fout("date.out");

int L[101], E[101];
int n;

int main()
{
    fin >> n;
    for (int i = 0; i < n; i++) {
        fin >> L[i];
        E[i] = 1;
    }

    bool gata = false;
    while (!gata) {
        // Afisam configuratia curenta
        for (int i = 0; i < n; i++)
            fout << E[i] << ' ';
        fout << '\n';

        // Generam succesorul: cea mai din dreapta pozitie care poate creste
        int i = n - 1;
        while (i >= 0 && E[i] == L[i]) {
            E[i] = 1;
            i--;
        }
        if (i < 0) gata = true;
        else E[i]++;
    }

    return 0;
}

date.in:

3
2 3 2

date.out (primele linii):

1 1 1
1 1 2
1 2 1
1 2 2
...

Pas cu pas pentru (2, 3, 2)

Pas E Acțiune
0 1 1 1 Start
1 1 1 2 Creștem E[2]
2 1 2 1 E[2]=L[2], resetăm, creștem E[1]
3 1 2 2 Creștem E[2]
4 1 3 1 Resetăm E[2], creștem E[1]
5 1 3 2 Creștem E[2]
6 2 1 1 E[2]=L[2] și E[1]=L[1], resetăm, creștem E[0]
… … …

2. Submulțimi

Problema

Generăm toate submulțimile lui {1, 2, ..., n}.

Observație

O submulțime poate fi reprezentată cu un vector de n biți (caracteristic): E[i] = 1 dacă elementul i e în submulțime, 0 altfel.

Asta e echivalent cu un produs cartezian cu L = (2, 2, ..., 2) (fiecare poziție ia valori 0 sau 1).

Cod

#include <fstream>
using namespace std;
ifstream fin("date.in");
ofstream fout("date.out");

int E[101];
int n;

int main()
{
    fin >> n;

    // Pornim cu submultimea vida (toti 0)
    for (int i = 0; i < n; i++) E[i] = 0;

    bool gata = false;
    while (!gata) {
        // Afisam submultimea curenta
        fout << "{ ";
        for (int i = 0; i < n; i++)
            if (E[i] == 1)
                fout << (i + 1) << ' ';
        fout << "}\n";

        // Succesor: cresc cea mai din dreapta pozitie cu valoarea 0
        int i = n - 1;
        while (i >= 0 && E[i] == 1) {
            E[i] = 0;
            i--;
        }
        if (i < 0) gata = true;
        else E[i] = 1;
    }

    return 0;
}

date.in:

3

date.out:

{ }
{ 3 }
{ 2 }
{ 2 3 }
{ 1 }
{ 1 3 }
{ 1 2 }
{ 1 2 3 }

Total: 2^3 = 8 submulțimi.

3. Combinări

Problema

Generăm toate submulțimile de exact k elemente din {1, 2, ..., n}. În total, C(n, k) configurații.

Exemplu

n = 4, k = 2. Combinări:

(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)

Reprezentăm fiecare combinare ca vector crescător E[0] < E[1] < ... < E[k-1].

Algoritmul

  1. Inițializăm E = (1, 2, 3, ..., k) (prima combinare).
  2. Pentru succesor:
    • Găsim cea mai din dreapta poziție i cu E[i] < n - k + 1 + i (adică mai poate crește)
    • E[i]++
    • Pentru j > i: E[j] = E[j-1] + 1
  3. Dacă nicio poziție nu poate crește, STOP.

De ce n - k + 1 + i?

Pozițiile din dreapta lui i trebuie să fie strict mai mari decât E[i]. Ultima poziție (k-1) poate ajunge maxim la n, deci penultima la n-1, etc. Poziția i poate ajunge maxim la n - (k - 1 - i) = n - k + 1 + i.

Cod

#include <fstream>
using namespace std;
ifstream fin("date.in");
ofstream fout("date.out");

int E[101];
int n, k;

int main()
{
    fin >> n >> k;

    // Prima combinare: 1, 2, 3, ..., k
    for (int i = 0; i < k; i++)
        E[i] = i + 1;

    bool gata = false;
    while (!gata) {
        for (int i = 0; i < k; i++)
            fout << E[i] << ' ';
        fout << '\n';

        // Succesor: gasim cea mai din dreapta pozitie care mai poate creste
        int i = k - 1;
        while (i >= 0 && E[i] == n - k + 1 + i)
            i--;

        if (i < 0) gata = true;
        else {
            E[i]++;
            for (int j = i + 1; j < k; j++)
                E[j] = E[j - 1] + 1;
        }
    }

    return 0;
}

date.in:

4 2

date.out:

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

Pas cu pas pentru n=4, k=2

Pas E Acțiune
0 1 2 Start
1 1 3 E[1]<3, creștem E[1]
2 1 4 E[1]<4, creștem E[1]
3 2 3 E[1]=4, max, scădem la E[0]. E[0]=2, E[1]=3
4 2 4 Creștem E[1]
5 3 4 E[1]=4, max. E[0]=3, E[1]=4
6 STOP E[0]=3=n-k+1, E[1]=4=max

4. Permutări

Problema

Generăm toate permutările lui {1, 2, ..., n}. Sunt n! configurații.

Exemplu

n = 3. Permutări:

(1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1,2), (3,2,1)

Algoritmul clasic (lexicografic)

  1. Inițializăm E = (1, 2, 3, ..., n).
  2. Pentru succesor:
    • Găsim cea mai din dreapta poziție i cu E[i] < E[i+1]
    • Găsim cea mai din dreapta poziție j > i cu E[j] > E[i]
    • Interschimbăm E[i] și E[j]
    • Inversăm secvența de la i+1 la n-1
  3. Dacă nu există i, STOP.

Cod

#include <fstream>
using namespace std;
ifstream fin("date.in");
ofstream fout("date.out");

int E[101];
int n;

int main()
{
    fin >> n;

    for (int i = 0; i < n; i++)
        E[i] = i + 1;

    bool gata = false;
    while (!gata) {
        for (int i = 0; i < n; i++)
            fout << E[i] << ' ';
        fout << '\n';

        // Pas 1: gasim cel mai din dreapta i cu E[i] < E[i+1]
        int i = n - 2;
        while (i >= 0 && E[i] >= E[i + 1])
            i--;

        if (i < 0) { gata = true; continue; }

        // Pas 2: gasim cel mai din dreapta j > i cu E[j] > E[i]
        int j = n - 1;
        while (E[j] <= E[i]) j--;

        // Pas 3: swap E[i] si E[j]
        int tmp = E[i]; E[i] = E[j]; E[j] = tmp;

        // Pas 4: inversam E[i+1..n-1]
        int st = i + 1, dr = n - 1;
        while (st < dr) {
            tmp = E[st]; E[st] = E[dr]; E[dr] = tmp;
            st++; dr--;
        }
    }

    return 0;
}

date.in:

3

date.out:

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

Abordarea succesor vs backtracking

Ambele generează aceleași configurații. Diferențele:

Succesor Backtracking
Structură iterativă (while) recursivă
Ordine lexicografică directă lexicografică natural
Memorie O(n) O(n) stivă
Generalitate specifică problemei foarte generală
Simplitate medie mai ușor de înțeles inițial

Succesor e util când:

  • Vrei o soluție iterativă (fără stivă de apeluri)
  • Problema se pretează la “cel mai din dreapta…”
  • Vrei să salvezi memorie

Backtracking e util când condițiile sunt mai complexe.

Șablonul universal

Pentru orice problemă generativă de tip succesor:

// Inițializare: prima configurație
// ...

while (!gata) {
    // Afișăm configurația curentă
    // ...

    // Generăm succesorul:
    // 1. Găsim cea mai din dreapta poziție care "poate crește"
    // 2. Dacă nu există, gata = true
    // 3. Altfel: creștem acea poziție și resetăm/recalculăm pozițiile din dreapta
}

Greșeli frecvente

1. Inițializarea greșită

// Produs cartezian: trebuie sa incepem cu (1, 1, ..., 1)
for (int i = 0; i < n; i++) E[i] = 1;

// NU 0! pentru ca multimile sunt {1, 2, ..., L[i]}

2. Uitarea resetării

// Cand gasim pozitia i care poate creste, trebuie sa resetam din dreapta
while (i >= 0 && E[i] == L[i]) {
    E[i] = 1;  // uitarea asta duce la configuratii gresite
    i--;
}

3. Condiția pentru combinări

// GRESIT: if (E[i] < n) - nu tine cont de restrictiile pe urmatoarele pozitii
// CORECT: if (E[i] < n - k + 1 + i)

4. Ordinea afișare/generare succesor

while (!gata) {
    afiseaza();   // intai afisam
    calculeaza_succesor();  // apoi succesorul
}

Dacă inversezi ordinea, pierzi prima configurație sau o afișezi de două ori.

5. Confuzia E[i] vs E[i]-1 la indici

Dacă reprezentezi submulțimea cu vector binar, E[i] e 1 sau 0. Dar când afișezi elementul, e i+1 (pentru că mulțimea e {1, ..., n}, iar indicii vectorului încep de la 0).

Ce să reții

  • Algoritmii de tip succesor generează toate configurațiile unei probleme iterativ, în ordine lexicografică.
  • Ideea: pornim cu prima, la fiecare pas găsim cea mai din dreapta poziție care poate crește, o creștem și resetăm pozițiile din dreapta ei.
  • Aplicații clasice:
    • Produs cartezian: {1,...,L1} × ... × {1,...,Ln} - L1*L2*...*Ln elemente
    • Submulțimi: 2^n (caz particular cu L=(2,2,…,2))
    • Combinări: C(n, k) (vector strict crescător)
    • Permutări: n! (algoritm cu swap + reverse)
  • Alternativă la backtracking - iterativ, fără recursivitate.
  • Atenție la inițializare, reset și condiția de oprire.
Cuprins Inapoi Inainte