algorytm.org

Generowanie podzbiorów za pomocą Kodu Grey'a.

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?

Generowanie podzbiorów za pomocą Kodu Grey'a.
Ocena użytkowników:***** / 11
SłabyŚwietny 
Wpisany przez Krzysztof Kwiatkowski, 05 marca 2006 20:54

Kod Grey'a

Załóżmy, że mamy ciąg łańcuchów bitów. Jeżeli dwa kolejne łańcuchy z tego ciągu różnią się jednym bitem, to taki ciąg nazywać będziemy Kodem Grey'a.
Czyli np. dla łańcuchów 3 elementowych:
 B1B2B3 
1000łańcuch 1 - pierwszy element ciągu
2001 
3011 
4010łańcuch 4
5110łańcuch 5
6111 
7101 
8100 
Warto zauważyć dwa fakty:
  • Ilość elementów ciągu (ilość łańcuchów) zależna jest od ilości bitów w łańcuchu i równa jest 2^n, gdzie n-ilość elementów w łańcuchu.
    Z teorii mnogości wiadomo, że ilość podzbiorów zbioru n-elementowego jest równa 2^n. Czyli jest to pierwszy związek Kodu Grey'a z generowaniem podzbiorów.
  • Drugi fakt, zaoszczędzi nam czasu w obliczeniach. Zauważmy, że elementy 4-ty i 5-ty różnią się tylko na bicie B1, element 3-ci oraz 6-ty różnią się także tylko na bicie B1, tak samo jak element 2-gi i 7-dmy oraz 1-wszy i 8-smy.
    Wniosek: Wystarczy obliczyć elementy Kodu Grey'a do miejsca (2^n)/2, ponieważ kolejne łańcuchy można generować z już powstałych.
Generowanie kodu Grey'a może odbywać się poprzez generowanie wektora, w którym na k-tym miejscu znajduje się numer bitu, który należy zmienić w k-tym łańcuchu, aby uzyskać k+1-wszy łańcuch. Czyli dla powyższego przykładu wektor ten (zwany wektorem przejść) będzie miał postać:
[1,2,1,3,1,2,1]


Ponieważ każdy z łańcuchów kodu Gray’a jest unikalny oraz korzystając z tego, że ciąg Gray’a składa się z 2^n-tej elementów (dla n-elementowych łańcuchów), możemy wnioskować, że nadaje się on do generowania podzbiorów zbioru n-elementowego.
Załóżmy, że zbiór, którego podzbiory będziemy chcieli generować, będzie składał się z elementów B1, B2 oraz B3 (tak jak na powyższym przykładzie). Załóżmy także, że wystąpienie 1-dynki w kolejnym łańcuchu kodu Grey’a będzie oznaczało zawieranie odpowiedniego elementu w podzbiorze. Wtedy każde słowo kodu Gray’a będzie generowało podzbiór zbioru n-elementowego (w naszym przypadku 3 elementowego).

Czyli dla naszego przykładu wygenerowane podzbiory to odpowiednio:
  1. zbiór pusty
  2. B3
  3. B2,B3
  4. B2
  5. B1,B2
  6. B1,B2,B3
  7. B1,B3
  8. B1

Kod Gray'a można oczywiście wykorzystać do wyszukiwania podzbiorów k-elementowych, zbioru n-elementowego.

Generowanie pojedynczych słów kodu Gray’a.
Słowa kodu Gray'a nie koniecznie muszą być generowane poprzez generowanie wektora przejść. Więcej – nie trzeba ich generować iteracyjnie.
Poniższy przykład pokazuje jak wygenerować n-te słowo kodu Grey’a: Wygenerujmy 3-cie z kolei słowo (n=3) (licząc od zera):

1. Zamieniamy liczbę n na jej postać binarną n = 11

2. Przyjmujemy, że:
b(n) = 0 (w tym przypadku b(3) = 0)
Oraz wprowadzamy następujące oznaczenia (korzystając z postaci binarnej liczby n):
b(0) = 1
b(1) = 1
b(2) = 0
oraz b(3) = 0

3. Następnie obliczamy kolejne elementy łańcucha w kodzie Gray'a w następujący sposób:
( b(j) + ( b(j-1) ) mod 2 = g(j)
gdzie g(j) to j-ty element łańcucha, a j jest z przedziału (1; n).
Czyli dla naszego przykładu:
g(1) = (1+1) mod 2 = 0
g(2) = (0+1) mod 2 = 1
g(3) = (0+0) mod 2 = 0


4. n-te słowo Grey’a ma postać:
G = (g(1), g(2), g(3))
czyli dla naszego przykładu:
G=(0,1,0)

Teraz zróbmy taką konwersję w drugą stronę. Zamieńmy słowo Gray'a na jego indeks. Będziemy więc chcieli najpierw zamienić łańcuch na liczbę binarną, a później tę liczbę na liczbę dziesiętną.

1. Aby uzyskać :
- pierwszy bit tej liczby - sumujemy wszystkie (g(1) do g(n)) bity łańcucha i wykonujemy operację modulo 2
- drugi bit tej liczby - sumujemy g(1) ... g(n-1) i wykonujemy operację modulo 2
- trzeci bit tej liczby - sumujemy g(1) ... g(n-2) i wykonujemy operację modulo 2
- itd...

A więc dla naszego przykładu:
b(0) = (g(1) + g(2) + g(3)) = (0 + 1 + 0) mod 2 = 1
b(1) = (g(1) + g(2)) mod 2 = 1
b(2) = g(1) mod 2 = 0


2. Otrzymujemy liczbę binarną w postaci: 011, czyli dziesiętne 3.

W przykładzie zamieściłem funkcję konwertującą indeks kodu Gray'a na odpowiadający łańcuch oraz w łańcuch na indeks.

Przedstawiony sposób nie jest to może najszybszym sposobem generowania podzbiorów zbioru n-elementowego, ma natomiast jedną niesamowitą zaletę - jest bardzo prosty i po zrozumieniu zasady generowania kodu, można prawie natychmiast wygenerować dzięki niemu podzbiory.



Implementacje
AutorJęzyk
programowania
KomentarzOtwórzPobierzOcena
Krzysztof KwiatkowskiDelphi/Pascal
.pas
.pas
***** / 2
Krzysztof KwiatkowskiJava
.java
.java
***** / 2
 
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: 28 października 2012 15:31
Dodaj komentarz