algorytm.org

Porządek leksykograficzny

Baza Wiedzy
wersja offline serwisu przeznaczona na urządzenia z systemem Android
Darowizny
darowiznaWspomóż rozwój serwisu
Nagłówki RSS
Artykuły
Implementacje
Komentarze
Forum
Bookmarki






Sonda
Implementacji w jakim języku programowania poszukujesz?

Porządek leksykograficzny
Ocena użytkowników:***** / 18
SłabyŚwietny 
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:
  • 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
AutorJęzyk
programowania
KomentarzOtwórzPobierzOcena
Tomasz LubińskiAda
.ada
.ada
***** / 2
Rafał ŚwietlickiC/C++
.cpp
.cpp
***** / 4
 
Dodaj własną implementację tego algorytmu
  • Zaloguj się na stronie
Plik:
Język
programowania:
Komentarz:
  By móc dodać implementacje zaloguj się na stronie

Poprawiony: 19 lipca 2011 12:05
Komentarze
photo
-2 # bartek 2010-06-02 22:08
błąd w artykule, w def porządku leksykograficzn ego przyjmujemy indeks i większy równy 1 i mniejszy równy k (1
Odpowiedz | Odpowiedz z cytatem | Cytować
Dodaj komentarz