Matematyka dyskretna  kombinatoryka cz II
1
Generowanie obiektów kombinatorycznych
Przy omawianiu permutacji były podane trzy algorytmy generowania
zbioru wszystkich permutacji n elementów. Podamy teraz ogólne zasady
generowania obiektów kombinatorycznych.
Algorytmy generujące obiekty kombinatoryczne można podzielić na:
- algorytmy generujące wszystkie obiekty danej klasy - np.
wszystkie permutacje danych elementów
- generujące wybrany obiekt - może to być obiekt o podanym
mumerze dla przyjętego porządku
- generujące losowy obiekt w taki sposób, by prawdopodobieństwo
wylosowania każdego obiektu było jednakowe.
Na ogół generowanie wszystkich obiektów jest łatwiejsze niż
wygenerowanie pojedynczego. W algorytmach generujących wszystkie
obiekty zwykle wyróżniamy trzy etapy:
- inicjalizacja i wygenerowanie pierwszego obiektu
- przetworzenie wygenerowanego obiektu
- przejście od bieżącego obiektu do następnego
Generowanie podzbiorów
Każdemu elementowi przyporządkujemy 1 lub 0, zależnie od tego czy
należy lub nie należy do rozważanego podzbioru.
Stąd liczba k- elementowych podzbiorów tego zbioru jest równa liczbie
n bitowych liczb binarnych, w której k- razy występuje cyfra 1. Liczba
wszystkich podzbiorów utworzonych z n elementów, łącznie z
podzbiorem pustym, to liczba wszystkich n- bitowych liczb binarnych.
Matematyka dyskretna  kombinatoryka cz II
2
Przykład:
Zbiór znaków {a, b, c, d}, n=4 elementy. Liczba podzbiorów 24
=16. Podzbiór pusty jest reprezentowany przez liczbę 0000, dalsze
są podane w tabelce
liczba podzbiór liczba podzbiór liczba podzbiór
0001 d 0110 bc 1011 acd
0010 c 0111 bcd 1100 ab
0011 cd 1000 a 1101 abd
0100 b 1001 ad 1110 abc
0101 bd 1010 ac 1111 abcd
Generowanie losowego podzbioru. Jeżeli zbiór ma n elementów, to do
wylosowania jego losowego podzbioru wystarczy wylosować liczbę z
przedziału [0; 2n-1]. Elementami podzbioru są elementy odpowiadające
niezerowym bitom wylosowanej liczby.
Generowanie kombinacji.
Algorytm naiwny.
- generowanie wszystkich możliwych podzbiorów zbioru n-
elementowego
- wybranie podzbiorów k- elementowych
Algorytm ten wymaga wykonania znacznie większej pracy niż potrzeba
 dla zbioru n- elementowego wszystkich podzbiorów jest 2n, czyli
znacznie więcej niż kombinacji k- elementowych.
Przykład
Wyznaczyć wszystkie dwuelementowe kombinacje zbioru
{a, b, c, d} stosując algorytm naiwny.
Rozwiązanie:
Korzystamy z tabelki poprzednio wyznaczonych wszystkich podzbiorów
zbioru {a, b, c, d}.
Wybieramy podzbiory liczące 2 elementy. Są to:
{c,d} {b,d} {b,c} {a,d} {a,c} {a,b}.
Wszystkich podzbiorów jest 16, kombinacji tylko 6.
Matematyka dyskretna  kombinatoryka cz II
3
Generowanie kombinacji w porządku leksykograficznym.
Niech będzie dany zbiór S = {a, b, c, d, e, f }, a jego trójelementowe
będą reprezentowane przez ciągi tych elementów:
abc, abd, abe, abf, acd, ace, acf, ade adf aef, ... ,def
Kombinacje te zostały wypisane w porządku leksykograficznym. Każdej
kombinacji można przypisać numer w otrzymanym ciągu, zatem można
mówić o pewnym sposobie ich uporządkowania.
Niech elementami zbioru będą liczby 1,2, ..., n. Z tego zbioru chcemy
wyznaczyć kombinacje k- elementowe.
Algorytm wyznaczania ciągu kombinacji w porządku
leksykograficznym można teraz zapisać jako ciąg czynności:
- przyjmujemy początkową kombinację jako zbiór {1, 2, ..., k}
- bieżącą kombinację przekształcamy na następną według zasad:
- bieżącą kombinację przeglądamy od prawej do lewej, szukając
elementu który jeszcze nie osiągnął maksymalnej wartości
- element ten zwiększamy o 1, przy czym wszystkie elementy
leżące po jego prawej stronie otrzymują kolejno najmniejsze
dopuszczalne wartości
Przykład
a) S = {1, 2, 3, 4, 5} k=3;
Kombinacja początkowa: 123
Następne: 124 125 134 135 145 234 235 245 345
b) S = {1, 2, 3, 4, 5, 6} k=3;
Kombinacja początkowa: 123
Następne: 124 125 126 134 135 136 145 146 156
234 235 236 245 246 256 345 346 356 456
Matematyka dyskretna  kombinatoryka cz II
4
Generowanie kombinacji w porządku minimalnych zmian
Przy opisie tego algorytmu będziemy korzystali z reprezentacji binarnej,
tak jak przy opisie algorytmu generowania wszystkich podzbiorów.
Zatem 1 oznacza że dany element należy do zbioru, 0 ze nie należy.
Skorzystamy z kodu Gray a. Jest to sekwencja ciągów binarnych, w
której dwa kolejne ciągi różnią się dokładnie na jednej pozycji.
Kod Gray a tworzymy rekurencyjnie;
- dla n=2 mamy tylko dwa ciągi binarne
0 1
- jeżeli dla n > 1 mamy określone ciągi binarne C1, C2, ... ,Cm, to dla
n+1 tworzymy ciągi przez dopisanie do każdego z poprzednich, z
prawej strony:
0 do każdego ciągu C1, C2, ... ,Cm oraz
1 do każdego ciągu Cm, Cm-1, ... ,C1.
Stąd dla n+1 otrzymujemy ciągi
C10, C20, ... ,Cm0 , Cm1, Cm-11, ... ,C11
Wyniki dla n = 1, 2, ... , 5 są zestawione w tabeli
n Kody Gray a
1 0 1
2 00 10 11 01
3 000 100 110 010 011 111 101 001
4 0000 1000 1100 0100 0110 1110 1010 0010
0011 1011 1111 0111 0101 1101 1001 0001
5 00000 10000 11000 01000 01100 11100 10100 00100
00110 10110 11110 01110 01010 11010 10010 00010
00011 10011 11011 01011 01111 11111 10111 00111
00101 10101 11101 01101 01001 11001 10001 00001