Wypisanie wszystkich możliwych podziałów zbioru

Witam

Poszukuję algorytmu który określi wszystkie możliwe podziały zbioru n-elementowego.

Przykład dla zbioru 3-elementowego: {1,2,3}

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

Zszukałem się trochę po sieci jednak co znalazłem to liczbę Bella która określa jedynie ilość takich podziałów

rekurencja

Zapewne algorytm rekurencyjny, sądziłem że istnieją znane i eleganckie algorytmy do tego celu jak np. Heap's algorithm dla permutacji. W przypadku dużych porcji danych jak wiadomo szybkość algorytmu ma duże znaczenie. Przykładowo należało by w tym wypadku pominąć generowanie zbiorów {{1},{2,3}} i {{1},{3,2}} bo to te same zbiory.

@w0lter to akurat żaden problem, po prostu dodajesz do zbioru elementy tylko w kolejności rosnącej na przykład.

Rekurencja owszem ma swój koszt, ale jeżeli np stablicujesz sobie podziały dla zbiorów wielkości <= 7 (tych podziałów wyjdzie około tysiąca), a potem będziesz wykonywał tą rekurencję tylko dla większych podzbiorów, to jedno wywołanie wtedy średnio na wypisanie tysiąca podziałów wyjdzie około jedno - dwa wywołania rekurencyjne. Sam wzór Bella jest rekurencyjny, więc trudno by było zrobić nierekurencyjny program.

Dla N liczb.
Tablica liczb Tb na N elementów, liczba w tablice Tb[i] oznacza przynależność elementu i do zbioru o numerze T[i], gdzie i - 1..N
Stan początkowy T[i]=1 dla każdego i (odpowiada wariantu wszystkie należą do jednego zbioru).
W pętle:

szukasz od końca element T[i] taki dla którego istnieje T[k]=T[i], dla k - 1..(i-1)
jeżeli nie ma takiego to koniec pętli
zwiększasz znaleziony element T[i] o 1
wypełniasz jedynkami T[k], dla k - (i+1)..N
wyświetlasz zbiór.
koniec pętli.
A że mi się nudziło to napisałem kod w C++:

#include <iostream>
using namespace std;

void wypisz(char *T,int N)
  {
   cout<<'{';
   char p=0;
   bool f=false;
   for(int i=0;i<N;++i)
     {
      if(p!=T[i])
        {
         cout<<"},{";
         p=T[i];
         f=false;
        }
      if(f) cout<<",";
      cout<<(i+1);
      f=true;
     }
   cout<<'}'<<endl;
  }

void podzialy(int N)
  {
   int Nr=0;
   if((0<N)&&(N<=128))
     {
      char *T=new char[N];
      memset(T,0,N); // wyzerować wszystko
      while(true)
        {
         cout<<(++Nr)<<'\t'; // numer podziału
         wypisz(T,N);
         int i;
         for(i=N-1;i>=0;--i)
           {
            char f=T[i];
            if(f<N-1)
              {
               int k;
               for(k=0;k<i;++k)
                 {
                  if(T[k]==f) break; // mamy taką grupę
                 }
               if(k>=i) f=N;
              }
            if(f<N-1) // jeżeli mamy taką grupę
              {
               T[i]=f+1;
               for(int k=i+1;k<N;++k) T[k]=0;
               break;
              }
           }
         if(i<0) break;
        }
      delete[] T;
     }
  }

int main()
  {
   podzialy(5);
   cin.sync();
   cin.get();
   return 0;
  }

1	{1,2,3,4,5}
2	{1,2,3,4},{5}
3	{1,2,3},{4},{5}    <=====
4	{1,2,3},{4,5}
5	{1,2,3},{4},{5}    <=====
6	{1,2},{3},{4,5}
7	{1,2},{3},{4},{5} <------
8	{1,2},{3},{4},{5} <------
9	{1,2},{3,4},{5}

void wypisz(char *T,int N)
  {
   cout<<'{';
   for(int i=0;i<N;++i)
     {
      bool f=false;
      for(int k=0;k<N;++k)
        {
         if(T[k]==i)
           {            
            if(f) cout<<",";
            else if(i) cout<<",{";
            cout<<(k+1);
            f=true;
           }
        }
      if(!f) break;
      cout<<'}';
     }
   cout<<endl;
  }