rozpatrujemy ciagi n-elementowe binarne wiadomo ze istnieje kod Gray'a dla slow o dlugosci n ale ile istnieje roznych kodow Gray'a? kod Gray'a to taki kod, ze dwa sasiednie elementy ciagu roznia sie dokladnie jednym bitem (czyli odleglosc Hamminga = 1) (np jak mamy kod Gray'a to "obracajac" slowa otrzymamy tez kod Graya ale inny)
inne pytanie: ile jest roznych ciagow o wyrazach dlugosci n takich ze dwa sasiednie wyrazy roznia sie na dokladnie k bitach?
a jak w przypadku gdy slowa nie sa binarne, ale nad jakims alfabetem V o mocy m?
> [ciach bo tamto to byl szczegolny przypadek tego co bedzie ... ]
> inne pytanie: ile jest roznych ciagow o wyrazach dlugosci n takich > ze dwa sasiednie wyrazy roznia sie na dokladnie k bitach? > a jak w przypadku gdy slowa nie sa binarne, ale nad jakims alfabetem > V o mocy m?
1. Jesli mamy ten ciag liczb to wystarczy zagwarantowac aby liczba byla rozna na k pozycjach od poprzedniej, nie patrzac na nastepna, gdyz przy okreslaniu nastepnej bedziemy postepowali ta sama metoda (rekurencja)
2. Nie wazne czy dany bit jest rowny 1 czy 0 istotne jest tylko to czy jest inny (czy zachodzi sprzecznosc) niz ten poprzednika na danej pozycji
niech _ - oznacza pozycje na ktorej ma wystapic to samo co u poprzednika wyzej x - oznacza pozycje na ktorej ma wystapic bit przeciwny do bitu u poprzednika na tej samej pozycji
Rozpatrzmy taki przyklad (k = 2)
_ _ _ _ _ x x _ _ _ -> jako drugi wyraz w tym ciagu moze wystapic ( n - k ) roznych wyrazow tutaj np ten oraz : _ x x _ _ _ _ x x _ _ _ _ x x
nie zaleznie jaki ustawimy na jako 2 gi wyraz to i tak moze istniec znowuz ( n - k ) roznych wyrazow ktore moga wystapic jako wyraz nr 3. Gdyz mozemy postawic w danym miejscu _ niezaleznie czy byl tam x czy _ i tak samo mozemy postawic w dowolnym miejscu x. ( dzieki wprowadzeniu tej jakze pieknej wzglednosci - uniezaleznienie od konkretnych liczb zero jedynkowych)
a wiec poczawszy od drugiego wyrazu istnieje ( n - k ) ^ ( n - 1 ) roznych podciagow. Nalezy jeszcze przemnozyc to przez ilosc roznych wyrazow nr 1 w tym ciagu (gdyz dla kazdego z nich wystepuje tyle podciagow - poczawszy od wyrazu numer 2. A ile jest roznych wyrazow - slow nad alfabetem V o mocy m ? a wiec jest ich tyle ile jest wariacji z powtorzeniami n elementowych ze zbioru m elementowego, czyli m^n
Ostatecznie odpowiedz najogolniejsza jest nastepujaca (dla oznaczen jakie wprowadzil autor zadania)
( m^n ) * ( n - k ) ^ ( n - 1 )
tG^Mandrake
PS Mam nadzieje ze dobrze zrozumialem tresc zadania
LIST TEN JEST KONTYNUACJA PIERWSZEJ ODPOWIEDZI NA TEN PROBLEM Z UWZGLEDNIENIEM POPRAWEK NANIESIONYCH W LISTACH WCZESNIEJSZYCH NIZ TEN CO WLASNIE CZYTASZ (uzywa terminologii wprowadzonej w pierwszym liscie ale podchodzi do tego problemu przy uzyciu tych samych wprowadzonych definicji pelniej i poprawniej )
nalezy wiec znalezc ile istnieje dla danego wyrazu permutacji cyfr ( _ i x ) czyli poprawnych i sprzecznych (patrz o wzglednosci pierwszy moj list w tym topicu) Poniewaz musi wystepowac k cyfr x to mozemy to tak zobrazowac (alez to piekan rekurencja zagniezdzona :)))
x x | x _ _ _ x x | _ x _ _ x x | _ _ x _ x x | _ _ _ x x _ x |x _ _ x _ x |_ x _ ... itd
a wiec ich ilosc takich wyrazow otrzymamy sumujac
n - k + 1 + n - k + 1 - 1 + n - k + 1 - 2 +.....+ 1
jest to suma ciagu arytmetycznego o a1 = 1 i r = 1 , ilosc wyrazow = n - k + 1 wyznaczymy wiec te sume i oznaczmy ja przez S ( n, k , 2) (dla m = 2 )
Majac ilosc wyrazow sprzecznych na danym poziomie a wiedzac ze zmiana sytuacji na danym poziomie rozpoczyna cala nowa sytuacje na calym poddrzewu sytuacji dlatego ilosc roznych podciagow poczawszy od wyrazu nr 2 jest rowna losc poziomow (numerow wyrazu w ciagu) bez pierwszego czyli S ( n , k, m ) ^ ( n - 1 )
a poniewaz istnieje ( m^n ) roznych wyrazow nr 1 w tym ciagu to
istnieje ( m ^ n ) * [ S ( n , k, m ) ^ ( n -1 ) ]
pozostaje problem policzenia S(n , k, m) wiemy ze S ( n , k , 2 ) jest rowny sumie ciagu arytmetycznego. jesli m > 2 to na kazdej pozycji moze istniec (m - 1) roznych sprzecznych cyfr (bo wzgledem danej cyfry alfabetu o mocy m istnieje (m - 1) innych cyfr ) a poniewaz pozycji na jakich maja wystapic niezgodnosci jest zawsze k to S ( n , k , m ) = S ( n , k, 2 ) * [ ( m - 1 ) ^ k ] Policzmy dla formalnosci S ( n , k , 2) S ( n , k , 2) = 0.5 * [ 1 + (1+ [n - k]*1 ) ] * [ n - k + 1] = 0.5 * ( n - k + 2 )* ( n - k + 1 )
sprawdzmy dla przykladowych n = 5 i k = 2 oraz m = 2 mozemy recznie policzyc ze istnieje 10 roznych ulozen cyfr sprzecznych S ( 5, 2, 2 ) = 0.5 * (5-2+2)*(5-2+1) = 0.5 *5*4 = 10 :))))
ostatecznie mamy wiec ze
OGOLNY PRZYPADEK DLA DOWOLNEGO ALFABETU, DOWOLNEGO k wynik W to W (n , k, m ) = ( m ^ n ) * [ ( 0.5 * [ n - k + 2 ] * [ n - k + 1 ] * [ ( m - 1 ) ^ k ] ) ^ ( n - 1 ) ]
Prosze kogos o przeanalizowanie mojego toku myslenia
1. Jesli mamy ten ciag liczb to wystarczy zagwarantowac aby liczba byla rozna na k pozycjach od poprzedniej, nie patrzac na nastepna, gdyz przy okreslaniu nastepnej bedziemy postepowali ta sama metoda (rekurencja)
2. Nie wazne czy dany bit jest rowny 1 czy 0 istotne jest tylko to czy jest inny (czy zachodzi sprzecznosc) niz ten poprzednika na danej pozycji
niech _ - oznacza pozycje na ktorej ma wystapic to samo co u poprzednika wyzej x - oznacza pozycje na ktorej ma wystapic bit przeciwny do bitu u poprzednika na tej samej pozycji
takie oznaczenia gwarantuja nam elastycznosc i WZGLEDNOSC w rachunkach dalszych !!!
nalezy wiec znalezc ile istnieje dla danego wyrazu ustawien cyfr ( _ i x ) sprzecznych do poprzedniego. ( 1 )
Poniewaz musi wystepowac k cyfr x to mozemy to tak zobrazowac (alez to piekna rekurencja zagniezdzona :)))
x x | x _ _ _ x x | _ x _ _ x x | _ _ x _ x x | _ _ _ x x _ x |x _ _ x _ x |_ x _ ... itd
a wiec ich ilosc takich wyrazow otrzymamy sumujac
n - k + 1 + n - k + 1 - 1 + n - k + 1 - 2 +.....+ 1
jest to suma ciagu arytmetycznego o a1 = 1 i r = 1 , ilosc wyrazow = n - k + 1 wyznaczymy wiec te sume i oznaczmy ja przez S ( n, k , 2) (dla m = 2 )
Majac ilosc wyrazow sprzecznych na danym poziomie a wiedzac ze zmiana sytuacji na danym poziomie rozpoczyna cala nowa sytuacje na calym poddrzewu sytuacji dlatego ilosc roznych podciagow poczawszy od wyrazu nr 2 jest rowna losc poziomow (numerow wyrazu w ciagu) bez pierwszego czyli S ( n , k, m ) ^ ( n - 1 )
a poniewaz istnieje m^n roznych wyrazow poczatkowych (bedacych pierwszym wyrazem ciagu) ( m^n bo to ilosc waracji n elementowych ze zbioru m elementowego) w tym ciagu to istnieje :
( m ^ n ) * [ S ( n , k, m ) ^ ( n -1 ) ] ciagow spelniajacych warunki !!
pozostaje problem policzenia S(n , k, m) :
wiemy ze S ( n , k , 2 ) jest rowny sumie ciagu arytmetycznego. jesli m > 2 to na kazdej pozycji moze istniec (m - 1) roznych sprzecznych cyfr (bo wzgledem danej cyfry alfabetu o mocy m istnieje (m - 1) cyfr roznych niz ta ) a poniewaz pozycji na jakich maja wystapic niezgodnosci jest zawsze k to
S ( n , k , m ) = S ( n , k, 2 ) * [ ( m - 1 ) ^ k ]
Policzmy dla formalnosci S ( n , k , 2)
S ( n , k , 2) = 0.5 * [ 1 + (1+ [n - k]*1 ) ] * [ n - k + 1] = 0.5 * (n - k + 2 )* ( n - k + 1 )
sprawdzmy dla przykladowych n = 5 i k = 2 oraz m = 2 mozemy recznie policzyc, ze istnieje 10 roznych ulozen cyfr sprzecznych S ( 5, 2, 2 ) = 0.5 * (5-2+2)*(5-2+1) = 0.5 *5*4 = 10 :))))
ostatecznie mamy wiec ze
OGOLNY PRZYPADEK DLA DOWOLNEGO ALFABETU, DOWOLNEGO k wynik W to W (n , k, m ) = ( m ^ n ) * [ ( 0.5 * [ n - k + 2 ] * [ n - k + 1 ] * [ ( m - 1 ) ^ k ] ) ^ ( n - 1 ) ]
Prosze kogos o przeanalizowanie mojego toku myslenia
1. Jesli mamy ten ciag liczb to wystarczy zagwarantowac aby liczba byla rozna na k pozycjach od poprzedniej, nie patrzac na nastepna, gdyz przy okreslaniu nastepnej bedziemy postepowali ta sama metoda (rekurencja)
2. Nie wazne czy dany bit jest rowny 1 czy 0 istotne jest tylko to czy jest inny (czy zachodzi sprzecznosc) niz ten poprzednika na danej pozycji
niech _ - oznacza pozycje na ktorej ma wystapic to samo co u poprzednika wyzej x - oznacza pozycje na ktorej ma wystapic bit przeciwny do bitu u poprzednika na tej samej pozycji
takie oznaczenia gwarantuja nam elastycznosc i WZGLEDNOSC w rachunkach dalszych !!!
nalezy wiec znalezc ile istnieje dla danego wyrazu ustawien cyfr ( _ i x ) sprzecznych do poprzedniego. ( 1 )
Poniewaz musi wystepowac k cyfr x to mozemy to tak zobrazowac (alez to piekna rekurencja zagniezdzona :)))
x x | x _ _ _ x x | _ x _ _ x x | _ _ x _ x x | _ _ _ x x _ x |x _ _ x _ x |_ x _ ... itd
a wiec ich ilosc takich wyrazow otrzymamy sumujac
n - k + 1 + n - k + 1 - 1 + n - k + 1 - 2 +.....+ 1
jest to suma ciagu arytmetycznego o a1 = 1 i r = 1 , ilosc wyrazow = n - k + 1 wyznaczymy wiec te sume i oznaczmy ja przez S ( n, k , 2) (dla m = 2 )
Majac ilosc wyrazow sprzecznych na danym poziomie a wiedzac ze zmiana sytuacji na danym poziomie rozpoczyna cala nowa sytuacje na calym poddrzewu sytuacji dlatego ilosc roznych podciagow poczawszy od wyrazu nr 2 jest rowna losc poziomow (numerow wyrazu w ciagu) bez pierwszego czyli S ( n , k, m ) ^ ( n - 1 )
a poniewaz istnieje m^n roznych wyrazow poczatkowych (bedacych pierwszym wyrazem ciagu) ( m^n bo to ilosc waracji n elementowych ze zbioru m elementowego) w tym ciagu to istnieje :
( m ^ n ) * [ S ( n , k, m ) ^ ( n -1 ) ] ciagow spelniajacych warunki !!
pozostaje problem policzenia S(n , k, m) :
wiemy ze S ( n , k , 2 ) jest rowny sumie ciagu arytmetycznego. jesli m > 2 to na kazdej pozycji moze istniec (m - 1) roznych sprzecznych cyfr (bo wzgledem danej cyfry alfabetu o mocy m istnieje (m - 1) cyfr roznych niz ta ) a poniewaz pozycji na jakich maja wystapic niezgodnosci jest zawsze k to
S ( n , k , m ) = S ( n , k, 2 ) * [ ( m - 1 ) ^ k ]
Policzmy dla formalnosci S ( n , k , 2)
S ( n , k , 2) = 0.5 * [ 1 + (1+ [n - k]*1 ) ] * [ n - k + 1] = 0.5 * (n - k + 2 )* ( n - k + 1 )
sprawdzmy dla przykladowych n = 5 i k = 2 oraz m = 2 mozemy recznie policzyc, ze istnieje 10 roznych ulozen cyfr sprzecznych S ( 5, 2, 2 ) = 0.5 * (5-2+2)*(5-2+1) = 0.5 *5*4 = 10 :))))
ostatecznie mamy wiec ze
OGOLNY PRZYPADEK DLA DOWOLNEGO ALFABETU, DOWOLNEGO k wynik W to W (n , k, m ) = ( m ^ n ) * [ ( 0.5 * [ n - k + 2 ] * [ n - k + 1 ] * [ ( m - 1 ) ^ k ] ) ^ ( n - 1 ) ]
Prosze kogos o przeanalizowanie mojego toku myslenia
> rozpatrujemy ciagi n-elementowe binarne > wiadomo ze istnieje kod Gray'a dla slow o dlugosci n > ale ile istnieje roznych kodow Gray'a? > kod Gray'a to taki kod, ze dwa sasiednie elementy ciagu roznia sie dokladnie > jednym bitem (czyli odleglosc Hamminga = 1) > (np jak mamy kod Gray'a to "obracajac" slowa otrzymamy tez kod Graya ale
inny)
Szukana liczba jest ilością ścieżek Hamiltona po nieskierowanym grafie 2^n wierzchołków, w którym każdy wierzchołek jest stopnia n. (Wierzchołki reprezentują n-bitowe ciągi) Ilość krawędzi w tym grafie to s = 2^n * n / 2.
Spróbuję najpierw znaleźć ilość ścieżek Hamiltona w takim grafie zaczynających się na danym wierzchołku.
Ścieżki Hamiltona można tworzyć w taki sposób: Będąc w kolejnym wierzchołku x ścieżki, wybieramy jedną z k krawędzi incydentych z tym wierzchołkiem (niech będzie (x, y)) i idziemy nią do wierzchołka y. Następnie usuwamy z grafu wszystkie k krawędzie incydentne z wierzchołkiem x.
Z założenia przechodzimy wszystkie wierzchołki, więc usuniemy wszystkie s = 2^n * n / 2 krawędzi. Można zauważyć jednak, że w każdym kroku mamy tyle możliwości ruchu, ile krawędzi usuwamy. Poza tym, nigdy, poza ostatnim wierzchołkiem ścieżki Hamiltona nie ma takiej sytuacji, że nie ma już żadnego ruchu (z założenia).
Niech a_i oznacza ilość możliwości ruchu w i-tym kroku tworzenia ścieżki Hamiltona (pamiętając, że pierwszy wierzchołek mamy zadany), wtedy:
suma po i = 1 ... (2^n - 1) a_i = s = 2^n * n / 2
dla każdego i = 2 ... (2^n - 2) 0 < a_i <= n
a_1 = n a_(n^2 - 1) = 0
I tu już nie daję rady - mogą być różne rozkłady wartości kolejnych a_i - dla każdego rozkładu trzeba policzyć
iloczyn po i = 1 ... (2^n - 2) a_i
...zsumować wszystkie te iloczyny (dla różnych rozkładów) - i tyle właśnie IMHO jest ścieżek Hamiltona zaczynających się w danym wierzchołku w omawianym grafie.
Teraz pomnożyć tą wartość przez 2^n (od tylu wierzchołków może się ścieżka Hamiltona zaczynać) - i 'już' mamy wynik :-)
Jeśli moje przeczucie może mieć jakąkolwiek wartość - przeczuwam jakiś paskudny wzór niejawnej postaci.
Paweł Olchawa <ma...@wp.pl> wrote in message news:3c8d2e10@news.vogel.pl... > 1. Jesli mamy ten ciag liczb to wystarczy zagwarantowac aby liczba byla > rozna na k pozycjach od poprzedniej, nie patrzac na nastepna, gdyz przy > okreslaniu nastepnej bedziemy postepowali ta sama metoda (rekurencja)
> 2. Nie wazne czy dany bit jest rowny 1 czy 0 istotne jest tylko to czy jest > inny (czy zachodzi sprzecznosc) niz ten poprzednika na danej pozycji
Chyba brakuje uwzględnienia jeszcze faktu, że w kodzie Gray'a ciągi nie mogą się powtarzać, tj. poniższe nie jest kodem Gray'a:
00 01 10 00
może stąd za duży wynik (patrz niżej) - choć nie do końca zrozumiałem to co napisałeś.
> OGOLNY PRZYPADEK DLA DOWOLNEGO ALFABETU, DOWOLNEGO k > wynik W to > W (n , k, m ) = ( m ^ n ) * [ ( 0.5 * [ n - k + 2 ] * [ n - k + 1 ] * [ > ( m - 1 ) ^ k ] ) ^ ( n - 1 ) ]
dla n = 2, k = 1, m = 2 wychodzi 12, a powinno 8 - można ręcznie sprawdzić - poniżej wypisane w kolumnach te 8 kodów Gray'a:
Amon sie nie pofatygowal, ale ze temat ciekawy, to odwale czarna robote i sformuluje jego pytanie czysto:
Kod n-wymiarowy Gray'a to bijekcja
g : {0 ... 2^n-1} --> {0 1}^n
taka, ze g(k-1) i g(k) roznia sie dokladnie jedna/ wspolrzedna/, dla 0 \< k < 2^n. Kod Gray'a g nazywamy cyklicznym, gdy g(0) i g(2^n-1) tez roznia sie dokladnie jedna wspolrzedna.
Amon pytal o liczbe G(n) wszystkich n-wymiarowych kodow Gray'a. Mozna tez zapytac o rownie ciekawa liczbe CG(n) wszystkich n-wymiarowych, cyklicznych kodow Gray'a.
W niskich wymiarach mozna wyobrazac sobie {0 1}^n jako zbior wierzcholkow n-wymiarowej kostki, a jak ktos ma n-wymiarowa wyobraznie, to moze tak samo postapic w wymiarze n. Tak wiec na oko widac, patrzac na odcinek i kwadrat, ze
G(1)=2 CG(1)=0 G(2)=8 CG(2)=8
co zauwazyl juz Sliwtan.
Niech odtad n > 1.
Dla kazdej trojki uporzadkowanej wierzcholkow
u v w
n-kostki, takich, ze (u v) oraz (v w) sa krawedziami zorientowanymi n-kostki, liczba kodow i kodow cyklicznych Gray'a g, spelniajacych
g(0)=u g(1)=v g(2)=w
nie zalezy od wyboru trojki u v w, czyli jest rowna odpowiednio:
G'(n) = G(n)/(2^n * n * (n-1))
CG'(n) = CG(n)/(2^n * n * (n-1))
Moze to dobry kierunek, a moze sprowadza na manowce. Dla n=3 pozwala latwo sprawdzic, ze:
G'(3) = 3 CG'(3) = 2
skad
G(3) = 144 CG(3) = 96
Dla wyzszych wymiarow metoda ta wymagalaby chyba programowania.
Chodzi mi po glowie inna, obiecujaca metoda. Moze w nastepnym liscie?
Pozdrawiam,
Wlodek
PS. Od lat kod Gray'a uparcie mi sie kojarzy z krzywa Hilberta. Czy moglby ktos temu przydac matematyczny sens? Niby k-ta dyskretna krzywa Hilberta jest cyklem (lub sciezka) w {0 ... 2^k-1}^2, i dla k=2 pokrywa sie z 2-wymiarowym Gray'em. Wiec moze chodzi o wspolne uogolnnienie na {0 ... 2^k-1}^n. Ale to za malo, to jeszcze nic nie znaczy. Chodzi raczej o istnienie odpowiednioego splaszczenia n-kostki.
-- ============= P o l N E W S ============== archiwum i przeszukiwanie newsów http://www.polnews.pl
>taka, ze g(k-1) i g(k) roznia sie dokladnie >jedna/ wspolrzedna/, dla 0 \< k < 2^n. Kod >Gray'a g nazywamy cyklicznym, gdy g(0) i g(2^n-1) >tez roznia sie dokladnie jedna wspolrzedna.
Powinno byc oczywiscie: ...dla 0 < k < 2^n
-- Wlodek
-- ============= P o l N E W S ============== archiwum i przeszukiwanie newsów http://www.polnews.pl
> Amon poruszyles niezwykle zajmujacy, atrakcyjny temat. > Ale napisales tak niechlujnie, ze sie odechciewa.
> Jezeli Ci zalezy na dyskusji, to sformuluj > pojecia i pytania porzadnie.
> -- Wlodek
Masz racje. postaram sie byc bardziej precyzyjny. rozwazmy zbior wszystkich slow binarnych (tzn nad alfabetem V={0,1}) jezeli ustawimy je w taki ciag, ze sasiednie elementy (slowa) ciagu roznia sie na dokladnie 1 pozycji to otrzymamy kod Gray'a ale kod Gray'a nie jest jednoznaczny, pytanie ile jest roznych kodow Gray'a. Pytanie mozna uogolnic na dowolny alfabet o mocy n oraz tak aby kolejne slowa roznily sie na dokladnie k pozycjach.
> I tu już nie daję rady - mogą być różne rozkłady wartości kolejnych a_i - > dla każdego rozkładu trzeba policzyć
... nie, bo nie każdy rozkład reprezentuje ilość możliwości w kolejnych krokach tworzenia ścieżki Hamiltona. Np. dla kostki 3 wymiarowej w pierwszym ruchu są zawsze 3 możliwości, w drugim __zawsze__ 2, w trzecim 2 lub 1 itd - wszystko pokazuje poniższe drzewo:
ma ono 3 * 2 * 3 = 18 liści na głębokości 2^3, stąd dla 3-wymiarowej kostki istnieje 18 ścieżek Hamiltona zaczynających się na danym wierzchołku, więc ogólnie wszystkich ścieżek Hamiltona jest 18 * 2^3 = 144, jak podawał W.Holsztyński
>rozwazmy zbior wszystkich slow binarnych (tzn nad alfabetem V={0,1})
o dowolnie ustalonej dlugosci n (n -- liczba naturalna)
>jezeli ustawimy je w taki ciag, ze sasiednie elementy (slowa) ciagu >roznia sie na dokladnie 1 pozycji to otrzymamy kod Gray'a
Jezeli dodatkowo ostatni od pierwszego tez rozni sie w dokladnie jednym miejscu, to kod taki nazywamy cyklicznym kodem Gray'a.
Kod Gray'a moze miec praktyczne zastosowanie dla liczenia kilku funkcji na raz (nawet jednej), ktorych argumentami sa slowa binarne, gdy nie zmieniaja sie za wiele, gdy zamiast danego slowa za argument wziac slowo, ktore w jednym miejscu jest inne (zamiast 0 ma w tym miejscu 1, lub na odwrot). "Malo zmieniaja" nalezy rozumiec w sensie procesu wyliczenia wartosci, a nie samej wartosci. scisle powinienem powiedziec: funkcje, ktorych wyliczenie malo sie zmienia, gdy zamiast danego slowa-argumentu rozpatrzyc slowo sasiednie (rozniace sie tylko jednym bitem).
W takich przypadkach zwykla, leksykograficzna kolejnosc slow (leksykogeraficzna, to to samo co wedlug ich wielkosci w interpretacji zapisow calkowitoliczbowych o podstawie 2) nie jest optymalna bo np. po slowie 00111111 nastepuje slowo 01000000, ktore od poprzedniego rozni sie wieloma bitami. Wtedy nasze funkcje trzeba obliczac na nowo. Przy kolejnosci danej kodem Gray'a wystarczy je tylko nieznacznie zmodyfikowac.
Zanim sie policzy liczbe kodow Gray'a to warto zauwazyc, ze istnieje dla kazdej dlugosci n przynajmniej jeden taki kod, a dal n > 1 zawsze istnieje tez kod cykliczny. Latwo je skonstruowac rekursywnie, na wiele sposobow, czyli latwo z kodu dlugosci n zbudowac kod dlugosci n+1. W praktyce nmoze to byc niewygodne dla sporych n, bo dla n=20 nalezaloby trzymac w pamieci kod dlugosci ponad milion (co prawda dzis to glupstwo :-). Zamiast tego elegancka monografia Wilfa i Nijenhuisa (chyba tak sie pisze to nazwisko?) "Combinatorial Algorithms) podawal miedzy innymi serie algorytmow typu "NEXT". Dla kodow Gray'a podawala subrutyne, ktora miala jedno slowo za input i produkowala nastepne slowo gray'owskie, nie obciazajac pamieci komputera. Nie zawsze mialem te monografie pod reka (na ogol wcale :-), wiec czasem pisalem podobna rutyne na nowo. Sprobujcie napisac sobie przynajmniej algorytm. Takie cwiczenie pozwala lepiej rozumiec strukture kombinatoryczna czy to liczb calkowitych czy tez kostkowych obiektow kombinatorycznych. Podobnie z permutacjami. Itd.
> ale kod Gray'a nie jest jednoznaczny, > pytanie ile jest roznych kodow Gray'a. > Pytanie mozna uogolnic na dowolny alfabet > o mocy n oraz tak aby kolejne slowa roznily > sie na dokladnie k pozycjach.
>Amon
Pozdrawiam,
Wlodek
-- ============= P o l N E W S ============== archiwum i przeszukiwanie newsów http://www.polnews.pl
|
