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

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

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

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

Jezeli Ci zalezy na dyskusji, to sformuluj
pojecia i pytania porzadnie.

-- Wlodek

Amon

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.

    Wlodek

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

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