Generowanie obiektów kombinatorycznych
Andrzej Szepietowski
W tym rozdziale zajmiemy si¸e algorytmami generujćymi (wypisuj¸acymi) obiekty kombinatoryczne. Przed-stawione algorytmy b¸ed¸a dzia laly wed lug nast¸epuj¸acego schematu:
• Wypisujemy pierwszy obiekt.
• Powtarzamy, aż do napotkania ostatniego obiektu:
Przetwarzamy bież¸acy obiekt tak, aby otrzymać nast¸epny obiekt.
Takie algorytmy maj¸a t¸a zalet¸e, że nie wymagaj¸a dużo pami¸eci. Należy tylko pami¸etać jeden obiekt.
Algorytmy generuj¸ace obiekty s¸a używane w przypadku, gdy chcemy sprawdzić wszystkie obiekty danej klasy lub wtedy, gdy chcemy wylosować obiekt danej klasy. Przypuśćmy, na przyk lad, że chcemy wylosować jakiś 3-podzbiór zbioru {1, . . . , 7}. W tym celu losujemy liczb¸e naturaln¸a od 1 do 7 = 35, a nast¸epnie 3
generujujemy podzbiory, aż do 35. elementu.
1
Generowanie podzbiorów
Zaczniemy od najprostszego przypadku wypisania wszystkich podzbiorów zbioru
{1, . . . , n}.
Algorytm wypisuj¸
acy wszystkie podzbiory zbioru {1, . . . , n}:
• Pierwszy podzbiór: ∅.
• by uzyskać nast¸epny po A podzbiór:
Wskazujemy na najwi¸eszy element nie należ¸acy do A, czyli a = max{i /
∈ A}
Jeżeli takiego a nie ma, to koniec algorytmu, zbiór A jest ostatnim podzbiorem.
W przeciwnym przypadku dodajemy a do A i usuwamy z A wszystkie elemenety wi¸eksze od a.
Dla n = 3 powyższy algorytm wypisze po kolei nast¸epuj¸ace zbiory: ∅ {3}, {2}, {2, 3}, {1}, {1, 3}, {1, 2},
{1, 2, 3}.
Zauważmy, że funkcje charakterystyczne wypisywanych podzbiorów, traktowane jako binarny zapis liczb, tworz¸a ci¸ag kolejnych liczb od 0 do 2n − 1. Szukaj¸ac nast¸epnego z kolei elemenetu algorytm post¸epuje podobnie jak algorytm zwi¸ekszania o jeden liczby w systemie dwójkowym.
1
Generowanie k-elementowych podzbiorów
Algorytm generuj¸
acy k elementowe podzbiory zbioru {1, . . . , n}:
• Pierwszy k-podzbiór to {1, . . . , k}.
• Przypuśćmy, że ostatnio wygenerowany podzbiór, to A = {a1, . . . , ak}, gdzie a1 < . . . < ak. Aby wygenerować nast¸epny podzbiór:
znajdujemy najmniejsze takie i, że ai + 1 /
∈ A;
jeżeli ai = n, to znaczy, że A = {n − k + 1, . . . , n} i jest to ostatni wygenerowany podzbiór.
jeżeli ai < n, to zwi¸ekszamy ai o jeden, a elementy mniejsze od ai zamieniamy na i − 1 najm-niejszych liczb, to znaczy aj := j dla j < i.
W przypadku, gdy n = 6 i k = 4 algorytm wypisze po kolei nast¸epuj¸ace podzbiory (podajemy je bez nawiasów i przecinków)
1234, 1235, 1245, 1345, 2345, 1236, 1246, 1346, 2346, 1256, 1356, 2356, 1456, 2456, 3456.
Zauważmy,że najpierw wypisywane s¸a 4-podzbiory niezawieraj¸ace 6:
1234, 1235, 1245, 1345, 2345
a później 4-podzbiory zawieraj¸ace 6
1236, 1246, 1346, 2346, 1256, 1356, 2356, 1456, 2456, 3456,
które otrzymywane s¸a w ten sposób, że do kolejnych 3-podzbiorów zbioru {1, . . . , 5} dopisywana jest 6.
Jest to ogólna zasada dzia lania tego algorytmu: aby wypisać j-podzbiory zbioru {1, . . . , i} algorytm najpierw wypisuje j podzbiory zbioru {1, . . . , i − 1}, a nast¸epnie podzbiory zawieraj¸ace element i, (śa one otrzymywane przez dodawanie i do j − 1 podzbiorów zbioru {1, . . . , i − 1}).
W powyższym przyk ladzie wśrod podzbiorów zawieraj¸acych 6 najpierw mamy te, które s¸a utworzone z 3-podzbiorów {1, 2, 3, 4} z dopisan¸a 6:
1236, 1246, 1346, 2346,
a po nich nast¸epuj¸a te, które s¸a utworzone z 2-podzbiorów {1, 2, 3, 4}, z dopisan¸a 5 i 6: 1256, 1356, 2356, 1456, 2456, 3456.
Dlatego, kiedy w bierz¸acym zbiorze A = {a1, . . . , ak} algorytm znalaz l takie i, że ai + 1 /
∈ A, to znaczy, że
algorytm jest w trakcie wypisywania tych podzbiorów, które zawieraj¸a ai+1, . . . , ak (wszystkie wi¸eksze od ai + 1), plus jakiś i-podzbiór zbioru {1, . . . , ai + 1}. Zbiór A jest ostatnim podzbiorem, w którym wyst¸epuj¸a ai+1, . . . , ak, oraz jakiś i-podzbiór zbioru {1, . . . , ai}, a nie wyst¸epuje ai + 1. Wed lug opisanej wyżej zasady teraz powinny nast¸apić podzbiory, które zawieraj¸a ai + 1 plus jakiś (i − 1)-podzbiór zbioru {1, . . . , ai}, plus elementy ai+1, . . . , ak. Pierwszy z nich to podzbiór
{1, . . . , i − 1, ai + 1, ai+1 . . . , ak}.
I taki element jest wypisywany po zbiorze A.
2
Generowanie permutacji
Algorytm generowania permutacji zbioru {1, . . . , n}:
• Pierwsza permutacja to ai = i, dla 1 ≤ i ≤ n.
• Aby wypisać nast¸epn¸a po (a1, . . . , an) permutacj¸e:
Znajdujemy najwi¸eksze j spe lniaj¸ace warunek aj < aj+1
jeżeli takiego j nie ma, to bierz¸aca permutacja jest ostatnia,
jeżeli takie j istnieje, to zamieniamy aj z najmniejszym ak takim, że ak > aj oraz k > j, a nast¸epnie odwracamy porz¸adek elementów aj+1, . . . , an.
Alorytm wypisuje permutacje w porz¸adku rosn¸acym, jeżeli potraktujemy permutacje jako liczby zapisane z baz¸a n + 1, a liczby 1, . . . , n jako cyfry w tym systemie.
Na przyk lad przypuśćmy, że bierz¸ac¸a permutacj¸a jest (436521). Algorytm znajduje j = 2 i aj = 3.
Wtedy ta permutacja jest ostatni¸a (najwi¸eksz¸a) permutacj¸a spośród permutacji zaczynaj¸acych si¸e od (43...), bo od pozycji trzeciej mamy ci¸ag malej¸acy (..6521) i jest to najwi¸ekszy ci¸ag jaki można utworzyć z elementów 1,2,5,6. Teraz powinny nast¸apić permutacje zaczynaj¸ace si¸e od (45....) (czwórki na pierwszym miejscu nie zmieniamy, a trójka na drugim miejscu powinna być zamieniona przez nast¸epn¸a spośrod liczb stoj¸acych za ni¸a, czyli przez 5). Pierwsz¸a tak¸a permutacj¸a jest ta, w której pozosta le elementy rosn¸a, czyli (451236).
Dla przyk ladu wypiszemy teraz 10 pierwszych permutacji czteroelementowych 1234, 1243, 1324, 1342, 1423, 1432, 2134, 2143, 2314, 2341, 2413, 2431, 4
Zadania
1. Wypisz wszystkie podzbiory zbioru {1, 2, 3, 4}.
2. Wypisz wszystkie 2-podzbiory zbioru {1, 2, 3, 4, 5}.
3. Wypisz 14 kolejnych permutacji zbioru {1, 2, 3, 4, 5, 6} poczynaj¸ac od permutacji 456321.
4. Napisz programy realizuj¸ace opisane w tym rozdziale algorytmy.
3