Generowanie podziałów zbioru

0

Mam taki oto problem.

Napisać program, który będzie generował wszystkie możliwe podziały n-elementowego zbioru. Oto, co mam z ksiazki od kombinatoryki dla programistów:

begin
  readln(n);
  for i:=1 to n do
    begin
      numerbloku[i]:=1;
      kierunek[i]:=true;
    end;
  nastepny[1]:=0;

  //wypisz podzial;

  j:=n;
  while j>1 do
    begin
      k:=numerbloku[j];
      if kierunek[j] then
        begin
          if nastepny[k]=0 then
            begin
              nastepny[k]:=j;
              poprzedni[j]:=k;
              nastepny[j]:=0;
            end;
          if nastepny[k]>j then
            begin
              poprzedni[j]:=k;
              nastepny[j]:=nastepny[k];
              poprzedni[nastepny[j]]:=j;
              nastepny[k]:=j;
            end;
          numerbloku[j]:=nastepny[k];
        end
      else
        begin
          numerbloku[j]:=poprzedni[k];
          if k=j then
            if nastepny[k]=0 then nastepny[poprzedni[k]]:=0
            else
              begin
                nastepny[poprzedni[k]]:=nastepny[k];
                poprzedni[nastepny[k]]:=poprzedni[k];
              end;
        end;

    //wypisz podzial;

      j:=n;
      while (j>1) and ((kierunek[j] and (numerbloku[j]=j))
      or (not kierunek[j] and (numerbloku[j]=1))) do
        begin
          kierunek[j]:=not kierunek[j];
          j:=j-1;
        end;
    end;
end.

nie mam pojcia co ma byc w miejscu,w ktorym wstawilem komentarz ( //wypisz podzial;), czy jakas procedura, czy rekurencyjnie ta proc. ma wywylywac sama siebie, a jezeli tak, to jak na koncu ma wypisywac wszystkie generowane podzialy.

Bylbym wdzieczny, gdy ktos mialby juz taki program gdzies w swoich archiwach, lub tez naprowadził mnie na wlasciwą droge ;)

Pozdrawiam

0

jak masz to z książki, to na pewno w książce masz opisane do czego stosowane są zmienne i jakiego są typu. Z tego co napisałeś nic nie da się wywnioskować.

0

A to najmocniej przepraszam ;)

Przed tym algorytmem napisano:

podzial zbioru {1..n} reprezentowac bedziemy przez ciag blokow uporzadkowanych weglug rozsnacego najmniejszego elementu w bloku. Ten najmniejszy element bloku nzywac bedzie numerem bloku. Zauwazmy ze numery kolejnych bolkow nie są na ogol kolejnymi liczbami naturalnymi. W algorytmie uzywac bedziemy zmiennych poprzedni[i], nastepny[i], 1 <= i <=n zawierajacych odpiowiednio numer poprzedniego i nastepnego bloku dla bloku o numerze i (nastepny[i]=0, jesli blok numer i jest ostatnim blokiem podzialu). dla kazdego elementu i, 1<=i<=n numer bloku zawierającego element i pamietany bedzie w zmiennej numerbloku[i], kierunek w jakim porusza sie element i zakodowany bedzie natomist w zmiennej boolowskiej kierunek[i] (kierunek[i]=true jesli i porusza sie do przodu)

Dane: n
Wyniki: ciag wszystkich podzialow zbioru {1..n} w ktorym kazdy nastepny podzial powstaje z poprzedniego przez przeniesienie pojedynczego elementu do innego bloku.

Nastepnie po algorytmie wymienionym w poscie wyzej:

Algorytm ten konstruuje najpierw podzial {1....n} (pętla 2) - zauwazmy, ze jest to pierwszy podzial na liscie Ln , utworzonej przez opisana przez nas konstrukcję rekurencji. Zadanie glownej petli (8) jest przesienienie aktyuwnego elementu j do sąsiedniego bloku - poprzedniego lub nastepnego (w tym ostatim przypadku moze zajsc potrzeba utworzenia nowego bloku postaci {j}) a nastepnie wyznaczenie aktywnego elementu w nowo powstałym podziale. Z opisanej kostrukcji rekurencyjnej wynika, ze dany element przesuwany jest tylko wtedy gdy wszystkie elementy od niego wieksze osiagają swe skrajne lewe lub prawe polozenie; dokladniej, element aktywny j* jest najmniejszym elementem takim, ze dla kazdego wiekszego elementu j jest spelniony jeden z nastepujacych dwoch warunkow:

kierunek[j] and (numerbloku[j]=j) tzn element j porusza sie do przodu i osiagnal swe skrajne polozenie na prawo (oczywiscie j nie moze byc elementem bloku o najmniejszym elemencie wiekszym niz j)
not kierunek[j] and (numerbloku[j]=1) tzn element j porusza sie do tylu o osiagnal swe skranje polozenie na lewo (w bloku pierwszym)

Zasada ta jest zrealizowana w wierszach 30-34. Przy okazji jest zmieniany poruszania sie elementow j>j*. Dodatkowo warunkiem w petli 31 jest j>1, gdyz z samej reprezentacji podzialu wynika, ze j=1 nie moze byc elementem aktywnym(element 1 jest oczywioscie zawsze elemenetem bloku numer 1) Jesli kazdy z elementow j>1 spelnia warunek 1 lub 2, to latwo sie przekonac , ze wszystkie podzialy zostaly juz generowane. W takim przypadku po wyjsciu z petli 31 mamy j=1 i nastepuje wyjscie z glownej petli 8 tzn zakonczenie dzialania algorytmu. Z konstrukcji rekurencji wynika tez latwo, ze elementem aktywnym dla pierwszego podzialu listy Ln tzn dla {{1,...,n}} jest e;lement n. Taka tez wartosc przypisywana jest zmiennej j przed wejsciem do petli 8 (wiersz)

Przeanalizujmy teraz proces przesuwania elementu aktywnego (wiersz 9-28). Najpierw znajduje sie numer k bloku zawierajacego element aktywny. Jesli element ten porusza sie do przodu, to wystarczy przesunac go do bloku o numerze nastepny[k] (p. wiersz 19) lecz w dwoch pozostalych przypadkach zmienna nastepny[k] nalezy najpierw zmodyfikowac. pierwszy przypadek zachodzi, gdy nastepny[k]=0 tzn gdy k jest numerem ostatniego bloku podzialu. Wtedy j utworzy blok jednoelementowy- wystarczy przyjac nastepny[k]:=j i odpowiednio zaktualizowac wartosc zmiennych nastepny[j] i poprzedni[j] (p. wiersz 13). Podobny jest drugi przypadek w ktorym nastepny[k]>j. Warunek ten oznacza, ze wszystkie bloki na prawo od bloku numer k zawieraja elementy wieksze od j (wsystkie te elementy zajmuja swe skrajne prawe polozenie, w przeciwnym razie j nie byloby elementem aktywnym). Z konstrukcji rekurencyjnej latwo wynika, ze w przypadku tym nalezy utworzyc blok jednoelementowy zawierajacy j. Dokonywane jest to w bloku 16 (jedyna roznica w stosunku to przypadku pierwszego jest to, ze tym razem nowo utworzony blok nie jest ostatnim blokiem podzialu).

W sytuacji gdy element j porusza sie do tylu (p. wiersz 21) wystarczy przesunac go do poprzedniego bloku (p. wiersz 22) i dokonac odpowiedniej aktualizacji tablic poprzedni i nastepny, jesli j tworzyl blok jednoelementowy - ma to miejsce dokladnie wtedy, gdy numerbloku[j]=k=j, gdyz kazdy element m>j bloku numer j zostalby wybrany elementem aktywnym w petli 31.

Przepraszam za bledy i pozdrawiam !