Question

Você pode me dar um exemplo de algoritmo não-recursivo para gerar todos os subconjuntos de um conjunto dado?

Answer 1

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