Wpisany przez Rafał Świetlicki,
12 stycznia 2007 12:17
Porządek leksykograficzny można wykorzystać do rozwiązania niektórych problemów kombinatorycznych jak na przykład: wygenerowanie wszystkich permutacji danego zbioru skończonego, wszystkich podzbiorów takiego zbioru bądź tylko podzbiorów o określonej ilości elementów, wszystkich macierzy nad danym ciałem skończonym itd. Dokonuje się tego za pomocą słów nad określonym alfabetem uporządkowanych wg tego porządku.
Załóżmy, że dany jest alfabet, tj. pewien zbiór A = {a1, a2, ..., an} z uporządkowanymi rosnąco elementami (a1 < a2 < ... < an). Słowo s = s1s2...sk jest mniejsze leksykograficznie od słowa t = t1t2...tk, gdzie s1, s2, ..., sk, t1, t2, ..., tk są znakami ze zbioru A, jeżeli istnieje indeks i (1 ≤ i ≤ k) taki, że s1 = t1, ..., si – 1 = ti – 1 zaś si < ti.
Np.: nad alfabetem A = {‘x’, ‘y’, ‘z’} słowo „xyy” jest mniejsze od słowa „xzy”.
Istnieje prosty algorytm, który przekształca dane słowo na słowo następne w porządku leksykograficznym. Mając dane słowo s = s1s2...sk należy znaleźć największy indeks i (1 ≤ i ≤ k) taki, że si < an, znak si zastąpić następnym występującym po nim znakiem w alfabecie A, a znaki si+1, ..., sk zastąpić znakiem a1. Jeżeli takiego indeksu nie udało się znaleźć, to słowo s jest ostatnie (maksymalne) wg porządku leksykograficznego. Oczywiście punktem wyjścia jest najmniejsze słowo, czyli k – znakowe słowo złożone wyłącznie ze znaku a1. Oto przykład 3 – znakowych słów nad alfabetem A = {‘x’, ‘y’} uporządkowane leksykograficznie: „xxx”, „xxy”, „xyx”, „xyy”, „yxx”, „yxy”, „yyx”, „yyy”.
Jak łatwo zauważyć, przyjmując alfabet A = {0, 1} i generując wszystkie k – znakowe słowa nad tym alfabetem otrzyma się reprezentacje binarne kolejnych liczb naturalnych: 0, 1, ..., 2k – 1.
Mając wszystkie słowa k – znakowe nad alfabetem A = {0, 1} można wygenerować wszystkie podzbiory dowolnego zbioru k – elementowego. Niech Z = {z1, z1, ..., zk} będzie dowolnym zbiorem zaś s = s1s2...sk kolejnym słowem nad alfabetem A = {0, 1}. Wówczas do podzbioru P zbioru Z dodawany jest element zi, jeżeli si = 1.
W ten sposób dla zbioru 3-elementowego otrzyma się kolejno:
Aby wygenerować wszystkie permutacje zbioru Z = {z1, z1, ..., zk} wystarczy utworzyć wszystkie różnoznakowe słowa nad alfabetem A = {1, 2, .., k} uporządkowane wg porządku leksykograficznego. Słowem minimalnym jest oczywiście słowo s = (1,2,...k). Aby teraz utworzyć następne po słowie s = s1s2...sk słowo w porządku leksykograficznym, postępuje się następująco: należy wyznaczyć największy indeks i (1 ≤ i ≤ k) taki, że znaki si, si+1, ..., sk tworzą ciąg malejący. Jeżeli i = 1, to oznacza, że s jest ostatnim słowem w porządku leksykograficznym. Jeżeli i > 1, to spośród elementów si, si+1, ..., sk wybierany jest element najmniejszy większy od si – 1 i jest on zamieniany miejscami z elementem si – 1, a na koniec wśród elementów si, si+1, ..., sk dokonywana jest zamiana pierwszego z ostatnim, drugiego z przedostatnim, itd. aż zostaną zamienione miejscami dwa sąsiednie elementy albo jeden sam ze sobą.
Dla przykładu zostanie wyznaczona następna permutacja w porządku leksykograficznym po permutacji (s1, s2, s3, s4, s5, s6, s7) = (4,1,3,2,7,6,5).
Największy indeks i taki, że znaki si, si+1, ..., sk tworzą ciąg malejący jest równy 5 i jest to ciąg (7,6,5).
W ciągu tym najmniejszym elementem większym od si – 1 = s4 = 2 jest liczba 5, którą w permutacji należy zamienić z liczbą 2.
Po tej zamianie w nowoutworzonej permutacji (4,1,3,5,7,6,2) pozostało zamienić miejscami liczbę 7 z liczbą 2 i powstanie następna w porządku leksykograficznym po permutacji (4,1,3,2,7,6,5) permutacja (4,1,3,5,2,6,7).
Dla utworzenia wszystkich m – elementowych podzbiorów zbioru Z = {z1, z2, ..., zk} (1 ≤ m ≤ k) należy utworzyć wszystkie k – znakowe słowa s = s1s2...sk nad alfabetem A = {0, 1} zawierające dokładnie m jedynek i k – m zer. Następnie do podzbioru P zbioru Z dodawany jest element zi, jeżeli si = 1.
Słowa 3 – znakowe nad alfabetem {0, 1} zawierające dokładnie dwie jedynki uporządkowane wg porządku leksykograficznego to: „011”, „101”, „110”.
Słowem minimalnym będzie słowo mające na początku k – m zer a następnie m jedynek. Jeżeli m = k to słowo s złożone z k jedynek jest jedynym słowem, jakie da się utworzyć.
W przeciwnym razie postępujemy następująco:
Postępując wg powyższego algorytmu, jako następne po słowie s = 0101110 w porządku leksykograficznym dostaniemy słowo t = 0110011.
Załóżmy, że dany jest alfabet, tj. pewien zbiór A = {a1, a2, ..., an} z uporządkowanymi rosnąco elementami (a1 < a2 < ... < an). Słowo s = s1s2...sk jest mniejsze leksykograficznie od słowa t = t1t2...tk, gdzie s1, s2, ..., sk, t1, t2, ..., tk są znakami ze zbioru A, jeżeli istnieje indeks i (1 ≤ i ≤ k) taki, że s1 = t1, ..., si – 1 = ti – 1 zaś si < ti.
Np.: nad alfabetem A = {‘x’, ‘y’, ‘z’} słowo „xyy” jest mniejsze od słowa „xzy”.
Istnieje prosty algorytm, który przekształca dane słowo na słowo następne w porządku leksykograficznym. Mając dane słowo s = s1s2...sk należy znaleźć największy indeks i (1 ≤ i ≤ k) taki, że si < an, znak si zastąpić następnym występującym po nim znakiem w alfabecie A, a znaki si+1, ..., sk zastąpić znakiem a1. Jeżeli takiego indeksu nie udało się znaleźć, to słowo s jest ostatnie (maksymalne) wg porządku leksykograficznego. Oczywiście punktem wyjścia jest najmniejsze słowo, czyli k – znakowe słowo złożone wyłącznie ze znaku a1. Oto przykład 3 – znakowych słów nad alfabetem A = {‘x’, ‘y’} uporządkowane leksykograficznie: „xxx”, „xxy”, „xyx”, „xyy”, „yxx”, „yxy”, „yyx”, „yyy”.
Jak łatwo zauważyć, przyjmując alfabet A = {0, 1} i generując wszystkie k – znakowe słowa nad tym alfabetem otrzyma się reprezentacje binarne kolejnych liczb naturalnych: 0, 1, ..., 2k – 1.
Mając wszystkie słowa k – znakowe nad alfabetem A = {0, 1} można wygenerować wszystkie podzbiory dowolnego zbioru k – elementowego. Niech Z = {z1, z1, ..., zk} będzie dowolnym zbiorem zaś s = s1s2...sk kolejnym słowem nad alfabetem A = {0, 1}. Wówczas do podzbioru P zbioru Z dodawany jest element zi, jeżeli si = 1.
W ten sposób dla zbioru 3-elementowego otrzyma się kolejno:
- zbiór pusty;
- {z3}
- {z2}
- {z2, z3}
- {z1}
- {z1, z3}
- {z1, z2}
- {z1, z2, z3}
Aby wygenerować wszystkie permutacje zbioru Z = {z1, z1, ..., zk} wystarczy utworzyć wszystkie różnoznakowe słowa nad alfabetem A = {1, 2, .., k} uporządkowane wg porządku leksykograficznego. Słowem minimalnym jest oczywiście słowo s = (1,2,...k). Aby teraz utworzyć następne po słowie s = s1s2...sk słowo w porządku leksykograficznym, postępuje się następująco: należy wyznaczyć największy indeks i (1 ≤ i ≤ k) taki, że znaki si, si+1, ..., sk tworzą ciąg malejący. Jeżeli i = 1, to oznacza, że s jest ostatnim słowem w porządku leksykograficznym. Jeżeli i > 1, to spośród elementów si, si+1, ..., sk wybierany jest element najmniejszy większy od si – 1 i jest on zamieniany miejscami z elementem si – 1, a na koniec wśród elementów si, si+1, ..., sk dokonywana jest zamiana pierwszego z ostatnim, drugiego z przedostatnim, itd. aż zostaną zamienione miejscami dwa sąsiednie elementy albo jeden sam ze sobą.
Dla przykładu zostanie wyznaczona następna permutacja w porządku leksykograficznym po permutacji (s1, s2, s3, s4, s5, s6, s7) = (4,1,3,2,7,6,5).
Największy indeks i taki, że znaki si, si+1, ..., sk tworzą ciąg malejący jest równy 5 i jest to ciąg (7,6,5).
W ciągu tym najmniejszym elementem większym od si – 1 = s4 = 2 jest liczba 5, którą w permutacji należy zamienić z liczbą 2.
Po tej zamianie w nowoutworzonej permutacji (4,1,3,5,7,6,2) pozostało zamienić miejscami liczbę 7 z liczbą 2 i powstanie następna w porządku leksykograficznym po permutacji (4,1,3,2,7,6,5) permutacja (4,1,3,5,2,6,7).
Dla utworzenia wszystkich m – elementowych podzbiorów zbioru Z = {z1, z2, ..., zk} (1 ≤ m ≤ k) należy utworzyć wszystkie k – znakowe słowa s = s1s2...sk nad alfabetem A = {0, 1} zawierające dokładnie m jedynek i k – m zer. Następnie do podzbioru P zbioru Z dodawany jest element zi, jeżeli si = 1.
Słowa 3 – znakowe nad alfabetem {0, 1} zawierające dokładnie dwie jedynki uporządkowane wg porządku leksykograficznego to: „011”, „101”, „110”.
Słowem minimalnym będzie słowo mające na początku k – m zer a następnie m jedynek. Jeżeli m = k to słowo s złożone z k jedynek jest jedynym słowem, jakie da się utworzyć.
W przeciwnym razie postępujemy następująco:
- szukamy największego indeksu i (1 ≤ i ≤ k – 1) takiego, że si = 0 oraz si+1 = 1
- jeżeli takiego indeksu nie znajdziemy to oznacza, że słowo s jest słowem maksymalnym;
- w przeciwnym razie zamieniamy miejscami element si z elementem si+1 zaś elementy si+2, ..., sk przesuwamy cyklicznie o jedno miejsce w prawo do momentu otrzymania na początku samych zer (o ile przynajmniej jeden z elementów si+2, ..., sk jest równy zero) a następnie samych jedynek (o ile przynajmniej jeden z elementów si+2, ..., sk jest równy jeden).
Postępując wg powyższego algorytmu, jako następne po słowie s = 0101110 w porządku leksykograficznym dostaniemy słowo t = 0110011.
Implementacje
Autor | Język programowania | Komentarz | Otwórz | Pobierz | Ocena |
Tomasz Lubiński | Ada | .ada | .ada | ***** / 2 | |
Rafał Świetlicki | C/C++ | .cpp | .cpp | ***** / 4 |
Poprawiony: 19 lipca 2011 12:05