Vamos mostrar dois algoritmos não-recursivos para gerar todos os subconjuntos de um conjunto dado.
Considere o conjunto \(X = \{1,2,3,4\}\). Queremos implementar o seguinte código em C++:
#include <iostream>
#include <cmath>
#include <iterator>
#include <set>
#include <list>
#include <stack>
#include <queue>
using namespace std;
typedef set<int,less<int> > IntSet;
void printAllSubsetsUsingBits(IntSet&);
void printSubsets(queue< list<int> >&);
void printAllSubsetsUsingStackAndQueue(IntSet&);
int main(int argc, char* argv[])
{
IntSet set1;
set1.insert(1);
set1.insert(2);
set1.insert(3);
set1.insert(4);
cout << "Conjunto: [";
copy(set1.begin(), set1.end(), ostream_iterator<int>(cout," "));
cout << "]" << endl << endl;
cout << "Subconjuntos usando bits" << endl;
printAllSubsetsUsingBits(set1);
cout << endl<< "Subconjuntos usando pilha e fila" << endl;
printAllSubsetsUsingStackAndQueue(set1);
}
Algoritmo 1: Função "printAllSubsetsUsingBits".
Se um conjunto X possui N elementos, então existem 2^N subconjuntos de X. A função conta de 1 até 2^N, que podemos considerar como o índice do subconjunto. Para cada índice, percorre-se a representação binária do índice, adicionando o elemento se tivermos o dígito "1". Por exemplo, se o índice for igual a 5, como em binário temos que 5 é igual a 0101, apenas o primeiro e o terceiro elemento do conjunto seriam adicionados ao subconjunto 5.
Segue o código abaixo:
void printAllSubsetsUsingBits(IntSet& set1) {
unsigned int subsetCount = (unsigned int)pow(2, set1.size());
for (unsigned int i = 1; i <= subsetCount; i++) {
list<int> subset;
IntSet::iterator pos;
unsigned int bitIndex = 0;
for (pos = set1.begin(); pos != set1.end(); ++pos) {
int bit = (i & ( 1 << bitIndex )) >> bitIndex;
if (bit > 0) {
subset.push_back(*pos);
}
bitIndex++;
}
cout << "Subconjunto " << i << ": [";
copy(subset.begin(), subset.end(), ostream_iterator<int>(cout," "));
cout << "]" << endl;
}
}
Algoritmo 2: Função "printAllSubsetsUsingStackAndQueue".
Este algoritmo utiliza uma pilha e uma fila de subconjuntos para produzir todos os subconjuntos de um conjunto. Ele funciona da seguinte forma. Considere o conjunto \(X = \{a_1, ..., a_n\}\). Inicialmente, coloca-se na pilha os subconjuntos \(\{ \}\) e \(\{a_1\}\). Em seguida, começa-se a percorrer os \(a_2, ..., a_n\) elementos restantes e, para cada um deles, faz-se duas operações: retira-se todos subconjuntos da pilha e os coloca na fila; e coloca-se todos os subconjuntos da pilha, união com o elemento corrente, na fila. Por exemplo, após esta primeira iteração, teríamos os subconjuntos \(\{ \}\), \(\{a_1\}\), \(\{a_2\}\), e \(\{a_1, a_2\}\) na fila, e a pilha vazia. Se o próximo elemento não for o último, transfere-se todos os subconjuntos da fila para a pilha e reinicia-se o processo.
Segue o código abaixo:
void printSubsets(queue< list<int> >& Q) {
int i = 1;
while (!Q.empty()) {
list<int> subset = Q.front();
cout << "Subconjunto " << i << ": [";
copy(subset.begin(), subset.end(), ostream_iterator<int>(cout," "));
cout << "]" << endl;
Q.pop();
i++;
}
}
void printAllSubsetsUsingStackAndQueue(IntSet& set1) {
queue< list<int> > Q;
stack< list<int> > S;
list<int> emptyList;
S.push(emptyList);
list<int> listWithFirstElement;
listWithFirstElement.push_back(*set1.begin());
S.push(listWithFirstElement);
IntSet::iterator it = set1.begin();
for (++it; it != set1.end(); ++it) {
while (!S.empty()) {
list<int> subset1(S.top());
S.pop();
Q.push(subset1);
list<int> subset2(subset1);
subset2.push_back(*it);
Q.push(subset2);
}
IntSet::iterator nextIterator = it;
++nextIterator;
if (nextIterator != set1.end()) {
while (!Q.empty()) {
list<int> subset3(Q.front());
Q.pop();
S.push(subset3);
}
}
}
printSubsets(Q);
}
Quem quiser referência adicional sobre os containers STL (ex.: queue, stack, etc), podem consultar o livro "Thinking in C++", de Bruce Eckel, Volume 2, 2 Edição. Os links para download podem ser obtidos em: http://mindview.net/Books/TICPP/ThinkingInCPP2e.html