Algoritmi de tip succesor — generează pasul următor

De ce contează?

Privește kilometrajul unei mașini: 19.999 → 20.000. Cum s-a făcut saltul? Ultima cifră era 9, nu mai putea crește, așa că a revenit la 0 și a „împins" cifra din stânga. Mulți algoritmi de generare fac exact asta: pornesc de la o configurație și calculează, pas cu pas, configurația imediat următoare.

Ideea de succesor

A genera „prin succesor" înseamnă: am o configurație curentă (un șir de poziții) și vreau următoarea în ordine. Repet operația până nu mai există o următoare. Astfel parcurg toate configurațiile, în ordine, fără să le țin pe toate în memorie deodată.

Observația-cheie

Cheia e ordinea lexicografică (ca în dicționar). Succesorul unei configurații este cea mai mică configurație strict mai mare decât ea. Pentru numere în baza 10, asta înseamnă pur și simplu „adună 1".

Algoritmul pas cu pas

Generăm toate șirurile de 3 cifre binare (0/1), pornind de la 0 0 0. Succesorul se calculează ca la kilometraj, dar cu cifre 0 și 1:

v	0	1	0
	0	1	2

Configurație curentă. Căutăm cea mai din dreapta poziție care mai poate crește.

Regula succesorului:

Caută cea mai din dreapta poziție care nu e la maxim.
Crește-o cu 1.
Pune pe minim tot ce e la dreapta ei.

v	0	1	1
	0	1	2

Poziția 2 era 0 (sub maxim) → devine 1. Nimic la dreapta. Succesorul lui 0 1 0 este 0 1 1.

Pentru 0 1 1: poziția 2 e la maxim (1), poziția 1 e la maxim (1), poziția 0 e 0 → crește poziția 0, resetează restul: 1 0 0.

Implementare C++

#include <iostream>
using namespace std;

int v[20], n = 3, baza = 2;   // 3 pozitii, cifre 0..baza-1

bool succesor() {
    int i = n - 1;
    while (i >= 0 && v[i] == baza - 1) {  // sari peste pozitiile la maxim
        i--;
    }
    if (i < 0) return false;              // nu mai exista succesor
    v[i]++;                               // creste prima pozitie posibila
    for (int j = i + 1; j < n; j++) {
        v[j] = 0;                         // reset la minim ce e la dreapta
    }
    return true;
}

int main() {
    for (int i = 0; i < n; i++) v[i] = 0; // prima configuratie: 0 0 0
    do {
        for (int i = 0; i < n; i++) cout << v[i];
        cout << "\n";
    } while (succesor());
    return 0;                             // afiseaza 000,001,010,...,111
}

Complexitate

Operație	Timp	Spațiu
Un pas de succesor	O(n) în cel mai rău caz	O(n)
Toate configurațiile (bază `b`, `n` poziții)	O(bⁿ · n)	O(n)

Greșeli frecvente

Greșeli reale la generarea prin succesor:

Uiți resetul la dreapta. Dacă crești o poziție dar nu resetezi pozițiile din dreapta, sari peste configurații sau le repeți.
Condiția de oprire greșită. Fără if (i < 0) return false, indexul devine negativ și accesezi v[-1] → comportament nedefinit.
Confunzi maximul. Pentru baza b, valoarea maximă e b - 1, nu b. Comparația v[i] == baza nu se îndeplinește niciodată → buclă greșită.
Pornești de la o configurație neinițializată. Prima trebuie să fie cea minimă (toate 0), altfel ratezi configurații.

Recapitulare

Generarea prin succesor produce, pas cu pas, configurația următoare în ordine lexicografică.
Regula: crește cea mai din dreapta poziție sub maxim, resetează tot ce e la dreapta.
Te oprești când nicio poziție nu mai poate crește (toate la valoarea maximă).