Wypisanie wszystkich możliwych podziałów zbioru

Odpowiedz Nowy wątek
2011-03-26 16:31

Rejestracja: 9 lat temu

Ostatnio: 9 lat temu

0

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

Pozostało 580 znaków

0x001
2011-03-26 17:18
0x001
0

rekurencja

Pozostało 580 znaków

2011-03-26 18:07

Rejestracja: 9 lat temu

Ostatnio: 9 lat temu

0

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.

Pozostało 580 znaków

2011-03-26 19:20
Moderator

Rejestracja: 16 lat temu

Ostatnio: 7 minut temu

0

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


Masz problem? Pisz na forum, nie do mnie. Nie masz problemów? Kup komputer...

Pozostało 580 znaków

2011-03-26 19:40

Rejestracja: 15 lat temu

Ostatnio: 33 minuty temu

0

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.


"Programs must be written for people to read, and only incidentally for machines to execute." - Abelson & Sussman, SICP, preface to the first edition
"Ci, co najbardziej pragną planować życie społeczne, gdyby im na to pozwolić, staliby się w najwyższym stopniu niebezpieczni i nietolerancyjni wobec planów życiowych innych ludzi. Często, tchnącego dobrocią i oddanego jakiejś sprawie idealistę, dzieli od fanatyka tylko mały krok."
Demokracja jest fajna, dopóki wygrywa twoja ulubiona partia.

Pozostało 580 znaków

2011-03-27 14:07

Rejestracja: 14 lat temu

Ostatnio: 4 dni temu

1

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;
  }

Wykonuję programy na zamówienie, pisać na Priv.
Asm/C/C++/Pascal/Delphi/Java/C#/PHP/JS oraz inne języki.
edytowany 1x, ostatnio: Adam Boduch, 2020-04-15 13:30

Pozostało 580 znaków

2011-03-27 16:11

Rejestracja: 15 lat temu

Ostatnio: 4 miesiące temu

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}
Racja, ale problem tylko w wyświetlaniu, kod poniżej. - _13th_Dragon 2011-03-27 19:14

Pozostało 580 znaków

2011-03-27 19:14

Rejestracja: 14 lat temu

Ostatnio: 4 dni temu

0
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;
  }

Wykonuję programy na zamówienie, pisać na Priv.
Asm/C/C++/Pascal/Delphi/Java/C#/PHP/JS oraz inne języki.
edytowany 1x, ostatnio: _13th_Dragon, 2011-03-27 19:14

Pozostało 580 znaków

Biały Terrorysta
2016-02-09 08:20
Biały Terrorysta
0

Słabe to, bo dla 5 elementów, powinny być 52 wyniki.

Oj bardzo słabo ... z czytaniem ze zrozumieniem. - _13th_Dragon 2016-02-09 22:55

Pozostało 580 znaków

Odpowiedz

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0