Generarea submulțimilor


Editat de Candale Silviu (silviu) la data 2019-02-24

Problema:

Se dă un număr natural n. Să se genereze toate submulțimile mulțimii {1,2,3,...,n}.

Soluție:

Pentru rezolvare folosim metoda backtracking. Acest articol prezintă două metode de rezolvare.

Metoda 1

În vectorul soluție x[] vom memora pe rând câte o submulțime. Deoarece submulțimile au număr variabil de elemente, și vectorul soluție va avea un număr variabil de elemente.

  • semnificaţia vectorului soluție: x[] reprezintă la un moment dat o submulțime
  • condiții externe: x[k] în {1,2,..,n}, k între 1 și n;
  • condiții interne: x[k]>x[i], i între 1 și k-1. Deoarece condițiile interne se aplică pentru toate elementele vectorului soluție, este suficient ca x[k]>x[k-1], pentru k>1;
  • condiții de existența a soluției: fiecare variantă a vectorului soluție corespunde cu o submulțime. Orice valoare validă plasată în vectorul soluție conduce la o soluție.
void afis(int k){
    for(int i=1 ; i<=k ; ++i)
        cout << x[i] << " ";
    cout << endl;
}
bool valid(int k){
    if(k == 1)
        return true;
    if(x[k] > x[k-1])
        return true;
    return false;
}
void back(int k){
    for(int i=1;i<=n;++i)
    {
        x[k]=i;
        if(valid(k))
        {
            afis(k);
            back(k+1);
        }
    }
}

Constatăm că putem rafina condițiile externe; deoarece x[k]>x[k-1], condițiile devin:

  • Condiții externe: x[k] în {x[k-1]+1, ... , n}, k între 1 și n. Pentru a uniformiza algoritmul, considerăm de la început că x[0] = 0;
  • Condiții interne: nu mai avem condiții interne; funcția valid() nu mai este necesară;
  • Condiții de existența a soluției rămân aceleași.
void back(int k){
    for(int i=x[k-1]+1;i<=n;++i)
    {
        x[k]=i;
        afis(k);
        back(k+1);
    }
}

Să observăm că submulțimea vidă nu se regăsește printre soluțiile generate cu acest algoritm. Dacă este cazul, afișarea ei se poate face în afara algoritmului de generare.

Metoda 2

Această metodă se bazează pe observația că pentru fiecare submulțime a mulțimii date, {1,2,...,n} îi corespunde un șir de n biți, notat x[], astfel:

  • dacă bitul x[k] = 0, elementul k nu aparține submulțimii curente;
  • dacă bitul x[k] = 1, elementul k aparține submulțimii curente.

Reamintim că o mulțime cu n elemente are 2 n submulțimi.

Exemplificăm cu mulțimea {1,2,3,4}.

0 0000 {} 8 1000 {1}
1 0001 {4} 9 1001 {1,4}
2 0010 {3} 10 1010 {1,3}
3 0011 {3,4} 11 1011 {1,3,4}
4 0100 {2} 12 1100 {1,2}
5 0101 {2,4} 13 1101 {1,2,4}
6 0110 {2,3} 14 1110 {1,2,3}
7 0111 {2,3,4} 15 1111 {1,2,3,4}

Putem să generăm toate șirurile de n biți, iar pentru fiecare șir să construim submulțimea corespunzătoare. Generarea șirurilor se poate face în mai multe moduri:

  • parcurgem numerele de la 0 la 2n-1 și transformăm fiecare număr în baza 2; obținem astfel pentru fiecare număr un șir de biți care va fi transformat în submulțime;
  • generăm direct șirul de biți cerut cu metoda backtracking.

Vom detalia mai jos rezolvarea cu backtracking:

  • semnificaţia vectorului soluție: x[] conține la un moment dat un șir de biți care va corespunde unei submulțimi
  • condiții externe: x[k] = 0 sau 1;
  • condiții interne nu există. Orice configurație parțială a vectorului x[] va conduce la o soluție validă
  • condiții de existență a soluției: k == n.
void afis(int k){
    for(int i=1 ; i <= k ; ++i)
        if(x[i] == 1)
            cout << i << " ";
    cout << endl;
}

void back(int k){
    for(int i = 0; i <= 1 ; ++i)
    {
        x[k]=i;
        if(k == n)
            afis(k);
        else
            back(k+1);
    }
}

Fișiere atașate


Probleme ataşate

Nr. Problema Clasa Dificultate Operații I/O
1 #0201 - SubmDiv 11 medie fișiere
2 #0198 - Submultimi 11 ușoară fișiere
3 #0204 - Siruri 11 medie fișiere
Editat de Candale Silviu (silviu) la data 2019-02-24