Jedną z
przydatnych cech silniowego systemu pozycyjnego jest jego bliskie pokrewieństwo z permutacjami zbiorów. Aby zrozumieć, skąd to się bierze przypuśćmy, że jesteśmy zainteresowani wygenerowaniem wszystkich permutacji pewnego zbioru w kolejności leksykograficznej. Można to robić na piechotę, poprzez wymyślanie kolejnych takich permutacji. Jest to jednak niewygodne i mało efektywne, dlatego zależy nam na znalezieniu metody mapowania tych permutacji w taki sposób, żeby móc szybko odpowiedzieć na pytanie „Jak wygląda n-ta permutacja tego zbioru”
Rozważmy permutację czterech elementów – a, b, c, d – i kolejność w jakiej te permutacje powstają. Oto tabela permutacji:
Rozważmy permutację czterech elementów – a, b, c, d – i kolejność w jakiej te permutacje powstają. Oto tabela permutacji:
0 abcd 6 bacd 12 cabd 18 dabc
1 abdc 7 badc 13 cadb 19 dacb
2 acbd 8 bcad 14 cbad 20 dbac
3 acdb 9 bcda 15 cbda 21 dbca
4 adbc 10 bdac 16 cdab 22 dcab
5 adcb 11 bdca 17 cdba 23 dcba
1 abdc 7 badc 13 cadb 19 dacb
2 acbd 8 bcad 14 cbad 20 dbac
3 acdb 9 bcda 15 cbda 21 dbca
4 adbc 10 bdac 16 cdab 22 dcab
5 adcb 11 bdca 17 cdba 23 dcba
Z początku nie widać żadnych zasad rządzących tymi wynikami, ale możemy dostrzec kilka wzorów – na przykład pierwsza litera permutacji zmienia się co sześć liter, a 3! = 6. Druga litera zmienia się co 2 permutacje, a 2! = 2.
Jeśli przepiszemy powyższą tabelę zastępując liczby porządkowe ich odpowiednikami w silniowym systemie pozycyjnym wszystko zaczyna się robić o wiele prostsze:
0000! abcd 1000! bacd 2000! cabd 3000! dabc
0010! abdc 1010! badc 2010! cadb 3010! dacb
0100! acbd 1100! bcad 2100! cbad 3100! dbac
0110! acdb 1110! bcda 2110! cbda 3110! dbca
0200! adbc 1200! bdac 2200! cdab 3200! dcab
0210! adcb 1210! bdca 2210! cdba 3210! dcba
0010! abdc 1010! badc 2010! cadb 3010! dacb
0100! acbd 1100! bcad 2100! cbad 3100! dbac
0110! acdb 1110! bcda 2110! cbda 3110! dbca
0200! adbc 1200! bdac 2200! cdab 3200! dcab
0210! adcb 1210! bdca 2210! cdba 3210! dcba
Wcześniej zauważyliśmy, że pierwsza litera zmienia się co 6 permutacji, a teraz widzimy, że pokrywa to się ze zmianą pierwszej cyfry z silniowym zapisie kolejnych liczb. Tak samo druga litera permutacji przemieszcza się, gdy dochodzi do zmiany wartości na drugiej pozycji w zapisie silniowym.
To podobieństwo zawdzięczamy konstrukcji zwanej „Kod Lehmera”, czyli sposobie oznaczania permutacji, który umożliwia jej odtworzenie. Oto co się kryje za „Kodem Lehmera” – przypuśćmy, że otrzymujemy możliwy do uporządkowania zabiór elementów, jak permutacja BEDAC złożona z liter od A – E. Zaczynamy od spojrzenia na pierwszą literę tej permutacji. Tutaj jest to B. Następnie sprawdzamy ile elementów tego zbioru jest mniejszych od B. W tem przypadku jest to tylko A. Tak więc oddzielamy B od naszej permutacji i zapisujemy, że jest większe od jednego elementu:
To podobieństwo zawdzięczamy konstrukcji zwanej „Kod Lehmera”, czyli sposobie oznaczania permutacji, który umożliwia jej odtworzenie. Oto co się kryje za „Kodem Lehmera” – przypuśćmy, że otrzymujemy możliwy do uporządkowania zabiór elementów, jak permutacja BEDAC złożona z liter od A – E. Zaczynamy od spojrzenia na pierwszą literę tej permutacji. Tutaj jest to B. Następnie sprawdzamy ile elementów tego zbioru jest mniejszych od B. W tem przypadku jest to tylko A. Tak więc oddzielamy B od naszej permutacji i zapisujemy, że jest większe od jednego elementu:
B EDAC
1
Teraz powtarzamy ten proces dla EDAC. E jest większe od 3 elementów zbioru, więc zapisujemy:
BE DAC
13
Powtarzamy dla DAC:
BED AC
132
Powtarzamy dla AC:
BEDA C
1320 0
Powtarzamy dla C:
BEDAC
13200
1
Teraz powtarzamy ten proces dla EDAC. E jest większe od 3 elementów zbioru, więc zapisujemy:
BE DAC
13
Powtarzamy dla DAC:
BED AC
132
Powtarzamy dla AC:
BEDA C
1320 0
Powtarzamy dla C:
BEDAC
13200
Więc kodem Lehmera dla tej permutacji jest (1, 3, 2, 0, 0). Warto zauważyć, że długość kodu zawsze odpowiada długości permutacji.
Mając kod Lehmara permutacji można odwrócić ten proces i otrzymać permutację. Przypuśćmy, że mamy kod (3, 1, 0, 0) i chcemy otrzymać permutację zbioru ABCD. Aby to zrobić, szukamy na początku elementu większego od trzech innych elementów zbioru. Tutaj jest to D. Teraz mamy:
Mając kod Lehmara permutacji można odwrócić ten proces i otrzymać permutację. Przypuśćmy, że mamy kod (3, 1, 0, 0) i chcemy otrzymać permutację zbioru ABCD. Aby to zrobić, szukamy na początku elementu większego od trzech innych elementów zbioru. Tutaj jest to D. Teraz mamy:
D ABC
3
I kod (1, 0, 0). W takim razie szukamy elementu większego od jednego elementu zbioru. Daje nam to literę B.
DB AC
31
Kod zostaje skrócony do (0, 0). W takim razie pozostaje 2 razy wyszukać najmniejszy element zbioru, co daje kolejno A i C. Otrzymujemy gotową permutację:
DBAC
3100
3
I kod (1, 0, 0). W takim razie szukamy elementu większego od jednego elementu zbioru. Daje nam to literę B.
DB AC
31
Kod zostaje skrócony do (0, 0). W takim razie pozostaje 2 razy wyszukać najmniejszy element zbioru, co daje kolejno A i C. Otrzymujemy gotową permutację:
DBAC
3100
Tak więc DBAC odpowiada kodowi Lehmera (3, 1, 0, 0). Co ciekawe, jak mogliśmy zauważyć wcześniej odpowiada też permutacji numer 20 przy posortowaniu wszystkich permutacji zbioru ABCD w kolejności leksykograficznej. Natomiast 20 to w zapisie silniowym 3100!.
Widząc już bezpośrednie powiązanie między silniowym systemem pozycyjnym a Kodem Lehmera otrzymujemy sposób na znajdowanie n-tej permutacji zbioru przy sortowaniu leksykograficznym. Skąd mamy jednak pewność, że dla każdego kodu takie mapowanie da poprawną kolejność leksykograficzną?
Widząc już bezpośrednie powiązanie między silniowym systemem pozycyjnym a Kodem Lehmera otrzymujemy sposób na znajdowanie n-tej permutacji zbioru przy sortowaniu leksykograficznym. Skąd mamy jednak pewność, że dla każdego kodu takie mapowanie da poprawną kolejność leksykograficzną?
Niech p1 i p2 oznaczają takie permutacje, że p1 > p2 przy sortowaniu leksykograficznym. L1 to kod Lehmera dla p1 a L2 to kod dla p2. Porównajmy te dwie permutacje i nazwijmy pierwszy element, w którym się nie zgadzają indeksem i.
Zauważmy, że indeksem i nie może być ostatni element, ponieważ oznaczałoby to, że zgadzają się na wszystkich pozycjach poza ostatnią, więc nie są permutacjami tego samego zbioru.
Jako że permutacje zgadzają się na pierwszych i – 1 pozycjach, kody Lemhera na pierwszych i – 1 pozycjach muszą być takie same. Kiedy permutacje nie zgodzą się na i-tej pozycji jej wartość dla permutacji p1 musi być większa niż wartość dla permutacji p2, bo p1 > p2, a ilość pozostałych elementów będzie taka sama dla obu permutacji. W takim razie kod dla i-tego elementu p1 będzie większy niż kod dla i-tego elementu p2, więc L1 > L2.
Zródło: http://www.keithschwarz.com Keith Schwarz
Zauważmy, że indeksem i nie może być ostatni element, ponieważ oznaczałoby to, że zgadzają się na wszystkich pozycjach poza ostatnią, więc nie są permutacjami tego samego zbioru.
Jako że permutacje zgadzają się na pierwszych i – 1 pozycjach, kody Lemhera na pierwszych i – 1 pozycjach muszą być takie same. Kiedy permutacje nie zgodzą się na i-tej pozycji jej wartość dla permutacji p1 musi być większa niż wartość dla permutacji p2, bo p1 > p2, a ilość pozostałych elementów będzie taka sama dla obu permutacji. W takim razie kod dla i-tego elementu p1 będzie większy niż kod dla i-tego elementu p2, więc L1 > L2.
Zródło: http://www.keithschwarz.com Keith Schwarz