Ilosc kodow Gray'a
mic...@poczta.onet.pl
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?
Amon
--
Wysłano z serwisu OnetNiusy: http://niusy.onet.pl
Paweł Olchawa
news:21f3.000011...@newsgate.onet.pl...
> [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
Paweł Olchawa
Przepraszam pomylilem sie ale tylko dla
m != 2 (tzn dla binarncyh jest ok) poniewaz potem moze rowniez wystepowac
wiele rodzajow niezgodnosci
...
pomysle i dam nowe rozwiazanie dla ogolnych poki co masz korekte , dla
binarnych :
( 2^n ) * ( n - k ) ^ ( n - 1 )
tG^Mandrake
sorry za zamieszanie, kazdy ma sie prawo pomylic
ale juz jest ok
Paweł Olchawa
tzn to nie musza byc kolejne pozycje te negujace
Wlodzimierz Holsztynski
Ale napisales tak niechlujnie, ze sie odechciewa.
Jezeli Ci zalezy na dyskusji, to sformuluj
pojecia i pytania porzadnie.
-- Wlodek
--
============= P o l N E W S ==============
archiwum i przeszukiwanie newsów
http://www.polnews.pl
Paweł Olchawa
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
Pozdrowienia tG^Mandrake (Paweł Olchawa)
Paweł Olchawa
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
Paweł Olchawa
Sliwtan
<mic...@poczta.onet.pl> wrote in message
news:21f3.000011...@newsgate.onet.pl...
> 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.
pzdr.
Sliwtan
Sliwtan
Paweł Olchawa <ma...@wp.pl> wrote in message news:3c8d...@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:
00 00 01 01 10 10 11 11
10 01 11 00 00 11 01 10
11 11 10 10 01 01 00 00
01 10 00 11 11 00 10 01
pzdr.
Sliwtan
Wlodzimierz Holsztynski
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.
Wlodzimierz Holsztynski
>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.
Powinno byc oczywiscie: ...dla 0 < k < 2^n
-- Wlodek
Paweł Olchawa
mogą
> się powtarzać, tj. poniższe nie jest kodem Gray'a:
>
> 00
> 01
> 10
> 00
>
Masz racje, tyle tylko ze nie wiedzialem o tym ze nie moga sie powtarzac...
Poprawie sie jak wroce dzisiaj ze szkoly bo chyba wiem jak to poprawic...
Dzieki
Pawel Olchawa
mic...@poczta.onet.pl
> 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.
Sliwtan
Sliwtan <sliwta...@wp.pl> wrote in message
news:a6jdpg$pn4$1...@news.tpi.pl...
>
>
> dla każdego i = 2 ... (2^n - 2) 0 < a_i <= n
powinno być 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ć
... 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:
.
.
. 1 - 1 - 0
/ /
3 - 2 - 2 - 1 - 2 - 1 - 1 - 0
\ \ \
. . 2 - 1 - 1 - 1 - 0
. . \
. . 2 - 0 (2 wierzchołki nie wykorzystane!)
\
1 - 0 (1 wierzch. nie wykorz.!)
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
Może takie drzewko w czymś pomoże...
pzdr.
Sliwtan
Wlodzimierz Holsztynski
> postaram sie byc bardziej precyzyjny.
Dziekuje.
>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,