Algorytm generowania podziałów

Struktura danych której obiekty reprezentują podziały zbioru {1,2,…,n}

Zbiór – lista liczb całkowitych

Operacje na zbiorze

• Dodaj liczbę

• Usuń liczbę

• Sprawdzenie, czy podana liczba należy do zbioru

• Spowodowanie, że zbiór staje się pusty

• Obliczenie liczby elementów zbioru

• Pokazanie zbioru

Implementacja zbioru na listach generycznych.

Podział – lista zbiorów

Operacje na podziale

• Znalezienie zbioru w podziale, do którego należy podana liczba

• Podanie pierwszego zbioru podziału

• Podanie zbioru w podziale, do którego należy liczba n

• Sprawdzenie, czy podany zbiór jest ostatni na liście podziału

• Obliczenie następnego po podanym zbioru w podziale

• Wygenerowanie podziału na singletony

• Usunięcie z podziału ostatniego zbioru

• Pokazanie podziału

• Dodanie podanego zbioru Z na koniec podziału P

Implementacja podziału na liście programowanej.

Następny podział – algorytm

następny(int n, Podział P)

Jeżeli n>1 to
{ Jeżeli n=2 to
{ Jeżeli P = { {1,2} } to P staje się podziałem { {1} , {2} } w przeciwnym przyp.
P staje się podziałem { {1,2} }
}
w przeciwnym przyp.
{ 1. Znajdź w P zbiór Z do którego należy n
2. Jeżeli Z nie jest ostatni w P to
2.1 usuń liczbę n ze zbioru Z
2.2 oblicz zbiór Z₁ następny w podziale P po zbiorze Z
2.3 dodaj do zbioru Z₁ liczbę n
3. Jeżeli Z jest ostatni i |Z|>1 to
3.1 usuń liczbę n ze zbioru Z
3.2 dodaj do podziału P na koniec zbiór {n}
4. Jeżeli Z jest ostatni i |Z|=1 to
4.1 usuń z podziału P zbiór ostatni Z={n}
4.2 następny(n-1,P)
4.3 oblicz pierwszy w podziale P zbiór Z
4.4 dodaj do Z liczbę n
}
}

Generowanie podziałów

1. Wczytanie n

2. Wygenerowanie podziału P zbioru {1,2,…,n} na singletony

3. Dopóki wczytana wartość dalej =1 wykonuj
   3.1 pokaz podział P
   3.2 następny(n, P)
   3.3 wczytaj wartość dalej