numer permutacji - algorytm
soft...@poczta.onet.pl
Mam dane w postaci wszystkich permutacji z powtórzeniami pewnego zbioru. Moje
permutacje charakteryzują się tym że elementów powtarzających się jest dużo,
np. w ciągu są dwie dwójki, dwie jedynki i trzydzieści zer. Do zapisania
wszystkich permuracji na dysku będzie potrzebne, jak dobrze liczę, (2 nad 34)*
(2 nad 32) * (30 nad 30) * (dwa bity na znak) * (ilość znaków) = 278256 * 2 *
34 = 18921408. Tymczasem wszystkich takich permutacji jest 278256 więc, jeśliby
istniał jakiś algorytm, każdej z nich można przypisać 19 bitową liczbę.
Wtenczas rozmiar byłby (ilość permutacji) * (19 bitów na permutację) = 278256 *
19 = 5286864, czyli ponad trzy razy mniejszy. I w związku z tym moje pytanie:
Czy istnieje jakiś algorytm generowania wszystkich permutacji z powtórzeniami w
takiej kolejności żeby później na podstawie numeru permutacji dałoby się w
prosty sposób ją ustalić? I w drugą stronę (na podstawie perumtacji otrzymać
jej numer), ze względu na obliczenia które muszę wykonać na tych permutacjach,
też bym potrzebował.
Z góry dziękuję za pomoc
Pozdrawiam
mario
--
Wysłano z serwisu OnetNiusy: http://niusy.onet.pl
Michał Śliwka
masz 30 zer
- przed którym zerem (albo na końcu) wstawić pierwszą dwójkę (4 bity)
- przed którym zerem (albo na końcu) wstawić drugą dwójkę (4 bity)
- przed którą cyfrą (albo na końcu) wstawić pierwszą jedynkę (5 bitów)
- przed którą cyfrą (albo na końcu) wstawić drugą jedynkę (5 bitów)
czyli razem 18 bitów
Tylko po co Ty chcesz zapisywać te wszystkie, jak mówisz - 'permutacje', na
dysku?
pzdr.
MŚ.
soft...@poczta.onet.pl
> masz 30 zer
> - przed którym zerem (albo na końcu) wstawić pierwszą dwójkę (4 bity)
> - przed którym zerem (albo na końcu) wstawić drugą dwójkę (4 bity)
> - przed którą cyfrą (albo na końcu) wstawić pierwszą jedynkę (5 bitów)
> - przed którą cyfrą (albo na końcu) wstawić drugą jedynkę (5 bitów)
> czyli razem 18 bitów
>
> Tylko po co Ty chcesz zapisywać te wszystkie, jak mówisz - 'permutacje', na
> dysku?
Witam
Pomysł jest dość ciekawy, jednak ja podałem tylko przykład takiej permutacji. W
rzeczywistości one będą trochę bardziej skomplikowane, choć powtarzających się
elementów będzie zawsze dużo. Pozatym chyba będzie potrzeba więcej bitów w
Twoim sposobie, gdyż przy pomocy 4 bitów można wskazać tylko jedną z szesnastu
pozycji. Dla trzudziestu pozycji konieczne jest pięć bitów. Czyli chyba to
powinno wyglądać w ten sposób:
- pierwszą dwójkę można wstawić w jedno z 31 miejsc - 5 bitów
- drugą dwójkę w jedno z 32 - 5 bitów
- pierwszą jedynkę w jedno z 33 miejsc - 6 bitów
- drugą dwójkę w jedno z 34 miejsc - 6 bitów
daje to 22 bity
Niech zdradzę co to za permutacje: to będą końcówki gry w warcaby. Chciałbym
znaleźć jakiś efektywny sposób zapisu ich na dysku. Jeśli dobrze policzyłem to
końcówek w których jest na planszy 6 lub mniej bierek jest niecałe 4*10^9, a to
może na moim 40GB dysku by się jakoś zmieściło, jakbym miał jakiś wydajny
sposób przechowywania ich.
dziękuję
pozdrawiam
Michał Śliwka
Użytkownik <soft...@poczta.onet.pl> napisał w wiadomości
news:56ff.000008...@newsgate.onet.pl...
> Witam
> Pomysł jest dość ciekawy, jednak ja podałem tylko przykład takiej
permutacji. W
> rzeczywistości one będą trochę bardziej skomplikowane, choć powtarzających
się
> elementów będzie zawsze dużo. Pozatym chyba będzie potrzeba więcej bitów w
> Twoim sposobie, gdyż przy pomocy 4 bitów można wskazać tylko jedną z
szesnastu
:-DD jak to pisałem to nie byłem jeszcze obudzony - myślałem, że 32 to 2^4
:-)
> Niech zdradzę co to za permutacje: to będą końcówki gry w warcaby.
Chciałbym
> znaleźć jakiś efektywny sposób zapisu ich na dysku. Jeśli dobrze
policzyłem to
> końcówek w których jest na planszy 6 lub mniej bierek jest niecałe 4*10^9,
a to
> może na moim 40GB dysku by się jakoś zmieściło, jakbym miał jakiś wydajny
> sposób przechowywania ich.
To problem robi się ciekawszy...
Napisz dokładniej, czy są to ciągi różnej długości, złożone z jakich znaków
(nad jakim alfabetem), i co ważne - jakie operacje chcesz wykonywać
na tej kolekcji ciągów: czy np. sprawdzanie, czy dany ciąg należy do
kolekcji,
czy może ważne na której jest pozycji w kolekcji, a może też na podstawie
początku ciągu chcesz wyszukać wszystkie zaczynające się w ten sposób itp.
pzdr.
MŚ.
soft...@poczta.onet.pl
> To problem robi się ciekawszy...
> Napisz dokładniej, czy są to ciągi różnej długości, złożone z jakich znaków
> (nad jakim alfabetem), i co ważne - jakie operacje chcesz wykonywać
> na tej kolekcji ciągów: czy np. sprawdzanie, czy dany ciąg należy do
> kolekcji,
> czy może ważne na której jest pozycji w kolekcji, a może też na podstawie
> początku ciągu chcesz wyszukać wszystkie zaczynające się w ten sposób itp.
Witam :)
Ciągi są zawsze stałej długości - wynika to z faktu że warcabnica ma zawsze
albo 64 pola, albo 100 pól; bierki można stawiać w tej grze tylko na połowie
pól, więc ciągi będą miały długość 32 albo 50 znaków. Kazdy ze znaków ma być
odpowiednikiem bierki na planszy w danym polu, lub informacją o tym że na polu
nie stoi żadna bierka. W warcabach mamy dwa rodzaje bierek: damki i pionki,
oczywiście dla każdego z gracza. Daje to pięć stanów w jakim może znajdować się
każde pole, więc ciągi moje są zawsze ustalonej długości nad alfabetem pięcio-
elementowym. Właściwie to wraz z takim ciągiem jeszcze będę musiał zapamiętać
która ze stron ma do wykonania ruch i która ze stron jest w wygranej pozycji
(zakładam że remisowych końcówek będzie najwięcej, więc tychże mógłbym nie
zapamiętać i po braku końcówki w bazie wnioskować że końcówka jest remisowa,
jednak jeśli bazę danych bym chciał wykorzystać do jakiś technik uogólniania
wiedzy (sieci neuronowe, alg. genetyczne), czy aproksymacji to domyślam się że
najwygodniej byłoby zapamiętać zupełnie wszystkie). Operacje które będę chciał
wykonywać na bazie tych końcówek (ciągów) to bardzo szybkie sprawdzanie czy
ciąg jest w bazie danych (najlepiej w czasie stałym, coś tak jak dostęp do
danych w tablicy mieszającej) i względenie szybkie dodawanie nowych końcówek
(myślę o jednokrotnym wygenerowaniu wszystkich końcowek, bez
późniejszego "samouczenia" programu, a algorytm do generowania końcówek mógłby
sobie popracować dłuższy okres czasu, w przeciwieństwie do algorytmu
przeszukiwania użytego podczas gry). Pomyślałem sobie że idealnym sposobem
byłoby traktowanie każdej końcówki jako permutacji o określonym numerze. Numer
ten byłby numerem kolejnym w sensie kolejności w której te permutacje by
generował jakiś algorytm. Jeśli do tego miałbym możliwość szybkiego ustalania
numeru każdej permutacji, to na dobrą sprawę samych permutacji nie musiałbym
nawet zapisywać na dysku czy w pamięci. Zapisywałbym tylko niezbędną,
wspomnianą już informację o tym czy końcówka jest wygrana i która ze stron ma
do wykonania następny ruch, a odszukiwałbym tą informację jedynie po numerze
permutacji - byłby on np indeksem w tablicy, bądź pozycją pliku.
dziękuję za odpowidź
Maciek
Użytkownik <soft...@poczta.onet.pl> napisał
w wiadomości news:56ff.00000c...@newsgate.onet.pl...
>
> > To problem robi się ciekawszy...
> > Napisz dokładniej, czy są to ciągi różnej długości, złożone z jakich
> > znaków (nad jakim alfabetem), i co ważne - jakie operacje chcesz wykonywać
> > na tej kolekcji ciągów: czy np. sprawdzanie, czy dany ciąg należy do
> > kolekcji,
> > czy może ważne na której jest pozycji w kolekcji, a może też na podstawie
> > początku ciągu chcesz wyszukać wszystkie zaczynające się w ten sposób itp.
>
> Witam :)
> pola, albo 100 pól; (....) więc ciągi będą miały długość 32 albo 50 znaków.
> Kazdy ze znaków ma być odpowiednikiem bierki na planszy w danym polu,
> lub informacją o tym że na polu nie stoi żadna bierka.
> stanów w jakim może znajdować się każde pole, więc ciągi moje są zawsze
> ustalonej długości nad alfabetem pięcio- elementowym.
A wiec dla planszy 8x8 musialbys zapamietac 32-"literowe" wyrazy.
Majac alfabet 5-znakowy potrzebujesz 3 bitow na znak (kod bierki).
To razem daje 32*5 = 160 bitow na uklad. Duzo.
Moznaby troche oszczedzic kodujac "znaki" (bierki) zmienna liczba
bitow (kod Huffmana). Wowczas prawdopodobnie pola puste kodowalyby sie
jednym bitem (np. zerowym), a pola zajete przez bierki - 3-bitowymi
ciagami, w ktorych pierwszy bit bylby '1', a pozostale dwa daja
cztery kombinacje przypisane pionom i damkom bialym i czarnym.
__Jezeli__ jednak z gory zakladasz, ze zapisujesz tylko koncowki
np. 6-bierkowe, to moze zamiast stanu planszy (na ktorej wiekszosc
danych to zera) zapamietuj pozycje bierek?
Uporzadkuj bierki np. w kolejnosci typow: biale piony, biale damki,
czarne piony, czarne damki - i zapamietaj liczbe bierek kolejnych
typow. Np. uklad: 2 piony B, 1 damka B, 2 piony C, 0 damek C zapisz:
(2, 1, 2, 0)
Kazdego typu bierek bedzie nie wiecej niz 6 (a nawet mniej, bo szesc
bierek jednego typu to pozycja koncowa gry), wiec na zapis kazdej
liczby wystarcza 3 bity - razem 12.
Dalej musisz zapisac pozycje kolejnych bierek na planszy - to bedzie
szesc liczb 5-bitowych (bo 5 bitow wystarcza do zapisania liczby
calkowitej z zakresu 0..31, czyli numeru porzadkowego pola planszy).
To daje 6*5 = 30 bitow.
Wraz z 12-bitowa tablica liczb bierek poszczegolnych typow
zmiescisz zapis pozycji w 42 bitach. To jest niecale 6 bajtow.
Pozostaje Ci jeszcze 6 bitow wolnych. :-))
Maciek
soft...@poczta.onet.pl
> A wiec dla planszy 8x8 musialbys zapamietac 32-"literowe" wyrazy.
> Majac alfabet 5-znakowy potrzebujesz 3 bitow na znak (kod bierki).
> To razem daje 32*5 = 160 bitow na uklad. Duzo.
> Moznaby troche oszczedzic kodujac "znaki" (bierki) zmienna liczba
> bitow (kod Huffmana). Wowczas prawdopodobnie pola puste kodowalyby sie
> jednym bitem (np. zerowym), a pola zajete przez bierki - 3-bitowymi
> ciagami, w ktorych pierwszy bit bylby '1', a pozostale dwa daja
> cztery kombinacje przypisane pionom i damkom bialym i czarnym.
Jednak kody huffmana dawały by zmienną długość każdego ciągu, nie wiem czy
potrafiłbym później szybko operować na takich ciągach różnej długości
> __Jezeli__ jednak z gory zakladasz, ze zapisujesz tylko koncowki
> np. 6-bierkowe, to moze zamiast stanu planszy (na ktorej wiekszosc
> danych to zera) zapamietuj pozycje bierek?
> Uporzadkuj bierki np. w kolejnosci typow: biale piony, biale damki,
> czarne piony, czarne damki - i zapamietaj liczbe bierek kolejnych
> typow. Np. uklad: 2 piony B, 1 damka B, 2 piony C, 0 damek C zapisz:
> (2, 1, 2, 0)
> Kazdego typu bierek bedzie nie wiecej niz 6 (a nawet mniej, bo szesc
> bierek jednego typu to pozycja koncowa gry), wiec na zapis kazdej
> liczby wystarcza 3 bity - razem 12.
> Dalej musisz zapisac pozycje kolejnych bierek na planszy - to bedzie
> szesc liczb 5-bitowych (bo 5 bitow wystarcza do zapisania liczby
> calkowitej z zakresu 0..31, czyli numeru porzadkowego pola planszy).
> To daje 6*5 = 30 bitow.
> Wraz z 12-bitowa tablica liczb bierek poszczegolnych typow
> zmiescisz zapis pozycji w 42 bitach. To jest niecale 6 bajtow.
> Pozostaje Ci jeszcze 6 bitow wolnych. :-))
Jeśli nie znajdę sposobu na szybkie znajdowane indeksu dla odpowiedniej
permutacji i permutacji na podstawie numeru, to właśnie zrobię w bardzo podoby
sosób jaki opisałeś, jednak wtenczas będę mógł zapamiętać co najwyżej pięcio-
bierkowe końcówki.
dziękuję
Michał Śliwka
Ja tylko zacznę - może ktoś dokończy.
Jest skończona liczba skończonych ciągów nad skończonym alfabetem. Jest to
więc język skończony, więc regularny, więc istnieje dla niego automat
rozpoznający go (stwierdzający czy dane słowo należy do języka), więc
istnieje automat minimalny rozpoznający ten język.
Wydaje mi się, że taki automat byłby dosyć dobrą strukturą do przechowywania
informacji, czy nany ciąg jest wygrywający dla pierwszego gracza, drugiego,
remisowy, lub w ogóle niemożliwy (miałby 4 takie stany końcowe)
Problem w tym, że trzeba najpierw mieć automat zbudowany 'normalnie' bez
patrzenia na minimalnośc, żeby go później zminimalizować. A to może zająć
sporo miejsca. Trzeba by więc pomyśleć o robieniu tego na raty.
Automat taki jest pewnym uleprzeniem innej struktury - USS - Uniwersalnej
Struktury Słownikowej.
To jest drzewo, w którym każda ścieżka od korzenia do liścia reprezentuje
słowo ze słownika. Węzeł W takiego drzewa to tablica k + 1 wskaźników do
dzieci, gdzie k to moc alfabetu. i-ty wskażnik może być null, to znaczy, że
nie ma słowa zaczynającego się od tego, co reprezentuje ścieżka od korzenia
do węzła W plus i-ta litera. k+1-wszy wskaźnik oznacza 'literę pustą',
jeśli jest niezerowy (to akurat może być 1 bit), to znaczy, że istnieje
słowo reprezentowane przez ścieżkę od korzenia do węzła W.
Myślę, że nie będziesz miał problemu ze znalezieniem w sieci dokładnego
opisu tej prostej struktury. Każdy węzeł będziesz mógł dosyć dobrze
upakować, skoro jest tylko 5 liter. Poza tym, masz stałą długość ciągów,
więc liście nie muszą mieć wskaźników, wystarczą bity. I jeszcze jedno -
wskaźniki można metodą prób i błędów zmniejszać - nie muszą to być
oczywiście zmienne 'unsigned int' 32 bitowe, jak standardowo ma to miejsce.
Chciałbym kiedyś dokończyć tą myśl o minimalnych autoamatach przechowujących
ciągi ale nie wiem, czy mi na to czas pozwoli...
pzdr.
MŚ.
Michał Śliwka
...
> rozpoznający go (stwierdzający czy dane słowo należy do języka), więc
> istnieje automat minimalny rozpoznający ten język.
> Automat taki jest pewnym uleprzeniem innej struktury - USS - Uniwersalnej
> Struktury Słownikowej.
Zapomiałem dodać - ale to już chyba widać - że sprawdzanie, czy słowo należy
do kolekcji trzymanej w tych strukturach jest w czasie proporcjonalnym do
długości słowa, czyli w Twoim przypadku w czasie stałym - wystarczy przejść
automat/dzrzewo.
pzdr.
MŚ.
soft...@poczta.onet.pl
Witam
Pomysły wydaje się bardzo ciekawy. Słyszałem kiedyś o problemie budowy
optymalnego automatu do wyszukiwania wzorca w ciągach znaków, jednak nie znam
dobrze tego zagadnienia i nie przyszło mi do głowy że istnieją algorytmy do
budowy takich automatów, a tym bardziej do automatów optymalnych w jakim
kolwiek sensie. Będę musiał zainteresować się tym zagadnieniem.
Bardzo ciekawy wydaje mi się też pomysł z wykorzystaniem struktury słownikowej,
jednak nie mogę potrafię oszacować rozmiaru takiej struktury i wydaje mi się że
jeślibym nie użył wskaźników to bym musiał na każdym poziomie w czasochłonny
sopsób obliczać pozycję następnego wezła.
Dziękuję bardzo za pomoc
soft...@poczta.onet.pl
Witam :)
Cały czas myślę jednak żeby zacząć budować taką bazę z wykorzystaniem
właśnie "numerów permutacji". Wymyśliłem jakieś algorytmy do generowania
wszystkich permutacji, jednak mam zupełną pustkę w głowie gdy myślę jak na
podstawie permutacji ustalić jej numer kolejny. Gdyby udało mi się jakoś
ustalać te numery to chyba bym miał strukturę dość wydają. Zupełnie mógłbym
pominąć zapisywanie informacji o ustawieniu bierek na planszy, po prostu każda
końcówka byłaby w miejscu z góry określonym. Zapisywałbym tylko wtenczas czy
końcówka jest wygrana, przegrna czy remisowa (dwa bity) i ile ruchów pozostało
do zkończenia gry, myślę że nie więcej niż 8 bitów (być może informacja o tym
ile ruchów pozostało do końca nie będzie nawet potrzebna, więc tylko dwa bity!)
Dla końcówek w których wykonują pierwszy ruch białe założyłbym oddzielny plik
niż dla końcówek w których pierwszy ruch wykonują czarne - tym sposobem bym
zaoszczędził kolejny bit dla każdej z końcówek. 10 bitów przemnożona przez
ilość końcowek (8*10^9) daje 8*10^10 bitów co daje 10GB danych. Jest to ilość
która zmieści się na dysku mojego domowego komputera. Jeśli do tych informacji
dodam informację o ustawieniu na planszy bierek (5+3)*6=48 bitów, to z rozmiaru
10GB zrobi mi się już 58GB - różnica jest duża. Pozatym zaczynam wątpić w to
żebym mógł sobie pozwolić na skomplikowane wyszukiwanie końcówki jeśli będą one
zapisane w pliku. Dostęp do dysku jest tak czasochłonny że chyba jedynie można
brać pod uwagę wyszukiwanie typu: "jedno nastawienie głowicy = jedna porcja
danych". Słyszałem co prawda o udostępnionych darmowych kontach shell do
testowania komputerów Compaq'a (nie wiem czy dobrze piszę nazwę tej firmy),
które mają 64GB pamięci RAM, jednak niebardzo sobie wyobrażam późniejsze
ściąganie takiej ilości danych od nich :)
Wydaje mi się że taki sposób zapamiętania byłby bardziej wydajny niż struktura
słownikowa. Prawdopodobnie rozmiar byłby mniejszy i z pewnością dostęp do
danych byłby o wiele szybszy. Problem tylko ze znalezieniem sposobu na
wyznaczanie numeru permutacji...
Kolejnym zagadnieniem byłaby próba uogólnienia tak zrobionej bazy danych.
Bardzo zaciekawił mie pomysł z budowaniem automatu, jednak nie znam tego
zagadnienia.
Andrzej Praszmo
[...]
> Wydaje mi się że taki sposób zapamiętania byłby bardziej wydajny niż
struktura
> słownikowa. Prawdopodobnie rozmiar byłby mniejszy i z pewnością dostęp do
> danych byłby o wiele szybszy. Problem tylko ze znalezieniem sposobu na
> wyznaczanie numeru permutacji...
Niech numer określony jest następująco:
Suma(i=1,6) [64*K(i)+32*R(i)+P(i)]*128^(i-1) -> 42bity
K(i) - kolor bierki 0-czarna 1-biała
R(i) - rodzaj bierki 0-pion 1-damka
P(i) - położenie bierki (0-31)
(jeżeli bierki nie ma, powtarzamy położenie poprzedniej)
Ilość "niemożliwych" czyli niewykorzystanych pozycji wynosi:
2^42-2^12*(32*31*30*29*28*27+32*31*30*29*28+
32*31*30*29+32*31*30+32*31+32) tj. ok. 37%,
za to jednak mamy prosty i szybki indeks.
Ale 2^42 to ok. 512GB licząc po jednym bicie na pozycję :-(
Z drugiej stronu dochodzi jednak możliwa kompresja (systemowa)
Z trzeciej :-) strony tablica jest trochę bez sensu.
Dla 6 bierek, komputer powinien sobie poradzić ze stwierdzeniem,
czy pozycja jest wygrywalna metodą "brute force"
--
Andrzej
soft...@poczta.onet.pl
> Numery permutacji nie muszą być kolejne.
> Niech numer określony jest następująco:
> Suma(i=1,6) [64*K(i)+32*R(i)+P(i)]*128^(i-1) -> 42bity
> K(i) - kolor bierki 0-czarna 1-biała
> R(i) - rodzaj bierki 0-pion 1-damka
> P(i) - położenie bierki (0-31)
> (jeżeli bierki nie ma, powtarzamy położenie poprzedniej)
> Ilość "niemożliwych" czyli niewykorzystanych pozycji wynosi:
> 2^42-2^12*(32*31*30*29*28*27+32*31*30*29*28+
> 32*31*30*29+32*31*30+32*31+32) tj. ok. 37%,
> za to jednak mamy prosty i szybki indeks.
>
> Ale 2^42 to ok. 512GB licząc po jednym bicie na pozycję :-(
> Z drugiej stronu dochodzi jednak możliwa kompresja (systemowa)
> Z trzeciej :-) strony tablica jest trochę bez sensu.
> Dla 6 bierek, komputer powinien sobie poradzić ze stwierdzeniem,
> czy pozycja jest wygrywalna metodą "brute force"
Tak się wydaje, prawda? Sześć bierek to tak mało że komputer powinien sobie
szybko wyliczyć metodą siłową... Jednak powiem Ci o pewnym fakcie który Cię
oszołomi :) Wczoraj wygenerowałem końcówki dla układów składających się z 4 lub
mniej bierek. Okazuje się że dla niektórych układów z trzema bierekami
głębokość drzewa gry wynosi 25 ruchów, a dla układow z czterema bierkami
czasami trzeba sprawdzić aż na 90 ruchów w głąb żeby przekonać się że końcówka
jest wygrana dla jednej ze stron. Jak się przyglądam tym końcówkom w których
przegranego trzeba "gonić" az przez 90 ruchów (tzn przez 45 ruchów dla każdej
ze stron) to jestem w niemałym szoku. Uruchamiałem mój program przeciwko innym
programom, żeby sprawdzić czy faktycznie będzie uciekał aż przez 90 ruchów.
Okazywało się zawsze że mój program szybko znajdował końcówkę remisową, a
goniący nie potrafił go "złapać". Gdy stawiałem mój program na pozycji wygranej
przeciwko innemu programowi to zawsze złapał przeciwnika, jednak z reguły o
wiele szybciej, gdyż prawdopodobnie przeciwnik nie wiedział że może uciekać aż
przez tak długi okres. Oczywiście swoich błędów w programie też nie wykluczam :)
W ogóle powstaje przy okazji ciekawe zagadnienie związane z samym generowaniem
końcowek. Jak można je w ogóle uzyskać skoro głębokość drzewa gry wynosi 90
poziomów? Ja osobiście bazuję na spostrzeżeniu że każdy z węzłów drzewa
powtarza się wielokrotnie w drzewach gry, co oznacza wspólne pod-problemy, a
więc można zastosować programowanie dynamiczne, bądź jakąś procedurę ze
spamiętywaniem. Metoda siłow z pewnością odpada :)
dziękuję
Maciek
> >
>
> Jeśli nie znajdę sposobu na szybkie znajdowane indeksu dla
> odpowiedniej permutacji i permutacji na podstawie numeru,
Dlugo trwalo zanim to napisalem, kawalek po kawalku.
No ale wreszcie jest. Prosze bardzo, oto sposob.
Na poczatek rozwazmy tylko rozstawienia n bierek, bez
rozrozniania typow bierek (czyli po prostu uklady zajetych pol).
Poniewaz na planszy sa 32 pola, to n pol mozna wybrac
na Z_n = (32 po n) = 32! / (n! * (32-n)!) sposobow.
Jak te rozstawienia ponumerowac (najlepiej kolejno)?
Najpierw numerujemy pola, od 0 do 31.
Nastepnie dzielimy wszystkie rozstawienia n-bierkowe na takie,
w ktorych pole 0 jest zajete, i takie, w ktorych jest wolne.
Do pierwszego zbioru nalezy (31 po (n-1)) rozstawien, do drugiego
zas (31 po n), zatem rozstawieniom z pierwszego zbioru nadamy
numery od 0 do (31 po (n-1))-1, zas rozstawieniom z drugiego
numery od (31 po (n-1)) do (32 po n)-1.
Rekurencyjnie (jesli n>1) w pierwszym zbiorze wydzielamy
podzbior (30 po (n-2)) rozstawien z zajetym polem 1 oraz
podzbior (30 po (n-1)) rozstawien z polem 1 wolnym, zas w drugim
zbiorze wydzielamy podzbior (30 po (n-1)) rozstawien z polem 1
zajetym oraz podzbior (30 po n) rozstawien z polem 1 wolnym; itd...
A zatem numer kolejny ukladu n zajetych pol (wsrod Z_n wszystkich
mozliwych rozstawien n-bierkowych) obliczamy tak:
1. na poczatek bierzemy numer N=0, a zajete pola szeregujemy
wedlug ich numerow (od najmniejszego do najwiekszego)
2. znajdujemy numer k1 pola, na ktorym stoi pierwsza bierka
(czyli najmniejszy sposrod numerow zajetych pol);
jesli bierka nie stoi na pierwszym polu planszy (k1>0),
to zwiekszamy N o liczbe rozstawien, w ktorych
zajete jest pole 0, lub pole 1, ... lub pole (k1-1):
N <- N + ((31-0) po (n-1))
N <- N + ((31-1) po (n-1))
...
N <- N + ((31-(k1-1)) po (n-1))
3. znajdujemy numer k2 pola, na ktorym stoi druga bierka;
jesli nie stoi ona bezposrednio za pierwsza (k2-k1>1),
to zwiekszamy N o liczbe rozstawien, w ktorych za polem k1
zajete jest pole (k1+1), lub (k1+2), ... lub (k2-1):
N <- N + ((31-(k1+1)) po (n-2))
N <- N + ((31-(k1+2)) po (n-2))
...
N <- N + ((31-(k2-1)) po (n-2))
4. znajdujemy numer k3 pola, na ktorym stoi trzecia bierka;
jesli nie stoi ona bezposrednio za druga (k3-k2>1),
to zwiekszamy N o liczbe rozstawien, w ktorych za polem k2
zajete jest pole (k2+1), lub (k2+2), ... lub (k3-1):
N <- N + ((31-(k2+1)) po (n-3))
N <- N + ((31-(k2+2)) po (n-3))
...
N <- N + ((31-(k3-1)) po (n-3))
5. ...i tak dalej, do wyczerpania wszystkich n zajetych pol.
Oczywiscie algorytm ten nalezy zamknac w podwojna petle, a jeszcze
lepiej wstepnie stablicowac wszystkie sumy naliczane w petli
wewnetrznej, i uproscic procedure do pojedynczej, n-krokowej petli.
"Spetlenie" algorytmu pojdzie latwiej gdy upodobnimy krok 2. do
nastepnych. Dokonujemy tego przez wyobrazone ustawienie przed
pierwsza bierka bierki "zerowej" na polu k0=-1.
Przeksztalcenie odwrotne, tj. wyznaczenie rozstawienia na podstawie
jego numeru, jest rownie proste:
1. sprawdzamy, czy numer rozstawienia jest mniejszy od (31 po (n-1));
jesli tak, to ustawiamy pierwsza bierke na pierwszym wolnym polu
(0) i przechodzimy do kroku 2.; a jesli nie, to od numeru
odejmujemy (31 po (n-1)), i sprawdzamy, czy zmniejszony
numer jest mniejszy od (30 po (n-1));
jesli tak, to ustawiamy pierwsza bierke na drugim wolnym polu
(1) i przechodzimy do kroku 2.; a jesli nie, to od numeru
odejmujemy (30 po (n-1)), i sprawdzamy, czy zmniejszony
numer jest mniejszy od (29 po (n-1));
jesli tak, to ustawiamy pierwsza bierke na trzecim wolnym polu
(2) i przechodzimy do kroku 2.; a jesli nie...
itd....
2. po ustawieniu pierwszej bierki zapamietujemy pole nastepne za nia
jako k, i sprawdzamy czy numer jest mniejszy od ((31-k) po (n-2));
jesli tak, to ustawiamy druga bierke na pierwszym wolnym polu
(k) i przechodzimy do kroku 3.; a jesli nie, to od numeru
odejmujemy ((31-k) po (n-2)), i sprawdzamy, czy zmniejszony
numer jest mniejszy od ((30-k) po (n-2));
jesli tak, to ustawiamy druga bierke na drugim wolnym polu
(k+1) i przechodzimy do kroku 3.; a jesli nie, to od numeru
odejmujemy ((30-k) po (n-2)), i sprawdzamy, czy zmniejszony
numer jest mniejszy od ((29-k) po (n-2));
itd....
3. po ustawieniu drugiej bierki zapamietujemy pole nastepne za nia
jako k, i sprawdzamy czy numer jest mniejszy od ((31-k) po (n-3));
jesli tak, to ustawiamy trzecia bierke na pierwszym wolnym polu
(k) i przechodzimy do kroku 4.; a jesli nie, to od numeru
odejmujemy ((31-k) po (n-3)), i sprawdzamy, czy zmniejszony
numer jest mniejszy od ((30-k) po (n-3));
jesli tak, to ustawiamy trzecia bierke na drugim wolnym polu
(k+1) i przechodzimy do kroku 4.; a jesli nie...
4. ...i tak dalej, do ustawienia wszystkich n bierek.
Te procedure tez latwo zapisac w postaci podwojnej petli,
no i oczywiscie warto miec stablicowane n+1 poczatkowych
wyrazow z 33 poczatkowych wierszy trojkata Pascala. :-)
Teraz pora zajac sie rozroznianiem typow bierek.
Mamy cztery typy bierek.
Zaleznie od potrzeb moga to byc biale piony, biale damki,
czarne piony i czarne damki, albo tez wlasne piony, wlasne
damki, piony przeciwnika i damki przeciwnika;
to drugie jest mozliwe dzieki srodkowej symetrii planszy.
Wobec tego na kazdym sposrod Z_n rozstawien n zajetych pol mamy 4^n
roznych ustawien bierek - wszystkich ustawien n-bierkowych jest wiec:
U_n = 4^n * Z_n = 4^n * (32 po n).
Wobec tego numerujemy typy bierek liczbami od 0 do 3, i kodujemy
typy bierek na planszy w postaci n-cyfrowej liczby czworkowej:
jesli pierwsza bierka jest typu T1, druga - T2, ..., enta - Tn
(wszystkie Ti naleza do zbioru {0, 1, 2, 3}), to zapisujemy
ten ciag typow jako liczbe:
T = T1 + 4*T2 + 16*T3 + ... + 4^(n-1)*Tn
To pozwala przypisac kazdej n-elementowej wariacji typow osobne Z_n
rozstawien. Na przyklad tak:
niech T oznacza numer kolejny wariacji typow (czyli ciag typow bierek),
zas N - opisany wyzej numer ich rozstawienia (numer kolejny ukladu n
zajetych pol). Wtedy numerem kolejnym N-tego rozstawienia T-tej
wariacji jest:
NR = T * Z_n + N.
W druga strone oczywiscie wyznaczamy ciag typow bierek T oraz numer
kolejny ich rozstawienia na planszy jako czesc calkowita ilorazu
oraz reszte z dzielenia numeru kolejnego ukladu NR przez Z_n.
W ten sposob mamy kolejno ponumerowane wszystkie mozliwe
n-bierkowe ustawienia na planszy. Teraz pozostaje tylko ulozyc
kolejno wszystkie ustawienia 1-bierkowe, 2-bierkowe, itd.
Ustawien 1-bierkowych jest U_1 = 4^1 * (32 po 1) = 128.
Ustawien 2-bierkowych jest U_2 = 4^2 * (32 po 2) = 7 936.
Ustawien 3-bierkowych jest U_3 = 4^3 * (32 po 3) = 325 504.
....
Ustawien 6-bierkowych jest U_6 = 4^3 * (32 po 6) = 3 927 502 720.
Teraz chyba juz bez trudu nadasz wszystkim ustawieniom
jednolita numeracje? :-) Powodzenia!
Maciek
przezro...@op.pl
Pomysły wydaje się być dobry. Raczej rozumiem ide którą przedstawileś. Nie
potrafię bez prób wdrożenia powiedzieć czy to na pewno będzie działało, ale
wydaje się że to jest właśnie sposób którego szukałem. Żałuję że nie mogę teraz
się tym zająć i teraz nie będę mógł sprawdzić tego pomysłu w praktyce (muszę
zajmować się projektami na których coś zarobię...) Mam nadzieję że najpóźniej w
przeciągu dwóch miesięcy wrócę do tego i z pewnością napiszę o rezultatach.
Rozważając tylko teoretycznie taką bazę końcówek, wydaje mi się że to może być
coś rewelacyjnego. Obserwowałem jak komputer zachowuje się gdy ma do dyspozycji
bazę końcówek cztero-bierkowych. O ile dobrze pamiętam to niektóre końcówk choć
są przegrane to komputer może bronić się przez około sto ruchów. Nie wydaje się
Wam to niesamowite? Ile ruchów będzie trzeba wykonać żeby doprowadzić niektóre
końcówki sześcio bierkowe do przegranej? 500 ruchów, a może jeszcze więcej?
Ciekawy też jestem bardzo jakby taką ogromną bazę danych można optymalizować
później. Na razie dzięki pomocy w powyższym liście wiem jak w ogóle taką bazę
danych zmieścić na dzisiejszym przeciętnym dysku :) Ciekawy jesetm bardzo czy
udałoby się zaprojektować jakąś sieć neuronową która by szybko się wyuczyła
takiej bazy danych i jakby ona się zachowywała na końcówkach których nie było w
próbie uczącej, np. na końcówkach 7 lub 8 bierkowych?
Mam nadzieję że za jakiś czas wrócę do pracy nad moim programem i obiecuję że
napiszę o wynikach :)
pozdrawiam
jeszcze raz dziękuję za wszelką pomoc
Mariusz Marszałkowski
Andrzej Lewandowski
>Dziękuję z ten list.
>
>Pomysły wydaje się być dobry. Raczej rozumiem ide którą przedstawileś. Nie
>potrafię bez prób wdrożenia powiedzieć czy to na pewno będzie działało, ale
>wydaje się że to jest właśnie sposób którego szukałem. Żałuję że nie mogę teraz
>się tym zająć i teraz nie będę mógł sprawdzić tego pomysłu w praktyce (muszę
>zajmować się projektami na których coś zarobię...) Mam nadzieję że najpóźniej w
>przeciągu dwóch miesięcy wrócę do tego i z pewnością napiszę o rezultatach.
>
[...]
>
>Mam nadzieję że za jakiś czas wrócę do pracy nad moim programem i obiecuję że
>napiszę o wynikach :)
>
>pozdrawiam
>jeszcze raz dziękuję za wszelką pomoc
>
>Mariusz Marszałkowski
A o czym to jest, bo widac tylko koniec a poczatku nie, a temat
jakby ciekawy?...
A.L.
Maciek
Użytkownik "Andrzej Lewandowski" <lewand...@attglobal.net>
napisał w wiadomości news:2mmrhvcftub26mvua...@4ax.com...
> On 22 Jul 2003 22:04:31 +0200, przezro...@op.pl wrote:
>
> >Dziękuję z ten list.
> >
> >Pomysły wydaje się być dobry. Raczej rozumiem ide którą przedstawileś.
> >Nie potrafię bez prób wdrożenia powiedzieć czy to na pewno będzie
> >działało, ale wydaje się że to jest właśnie sposób którego szukałem.
>
>
> A o czym to jest, bo widac tylko koniec a poczatku nie, a temat
> jakby ciekawy?...
http://niusy.onet.pl/niusy.html?t=watek&group=pl.sci.matematyka&tid=5781126
http://www.google.pl/groups?threadm=56ff.00000850.3ee40b1a%40newsgate.onet.pl
http://www.google.pl/groups?threadm=bdgm9g%24nva%241%40szmaragd.futuro.pl
Maciek
Maciek
W news:bfl9ps$n1h$1...@szmaragd.futuro.pl odpowiedziałem A.L.
na pytanie z news:2mmrhvcftub26mvua...@4ax.com...
> >
> > >
> > > [...]
> >
> > A o czym to jest, bo widac tylko koniec a poczatku nie,
> > a temat jakby ciekawy?...
>
>
> www.google.pl/groups?threadm=56ff.00000850.3ee40b1a%40newsgate.onet.pl
> www.google.pl/groups?threadm=bdgm9g%24nva%241%40szmaragd.futuro.pl
Swoja droga na ironie zakrawa, Andrzeju, ze zadajesz pytanie,
na ktore odpowiedz mozna od reki znalezc w Google'u. Akurat Ty,
ktorego niemal znakiem frmowym mogloby byc odsylanie do Google,
i ktory sam tu niedawno pisales:
"(...) Ale jak moge sam zalezc na googlu
w 15 sekund, to taki post mnie wkurza"
No nie? :-)
Maciek
Andrzej Lewandowski
<mac...@elkomtech.com.pl.nospam> wrote:
>
>>
>> www.google.pl/groups?threadm=56ff.00000850.3ee40b1a%40newsgate.onet.pl
>> www.google.pl/groups?threadm=bdgm9g%24nva%241%40szmaragd.futuro.pl
>
>
>Swoja droga na ironie zakrawa, Andrzeju, ze zadajesz pytanie,
>na ktore odpowiedz mozna od reki znalezc w Google'u. Akurat Ty,
>ktorego niemal znakiem frmowym mogloby byc odsylanie do Google,
>i ktory sam tu niedawno pisales:
>
> "(...) Ale jak moge sam zalezc na googlu
> w 15 sekund, to taki post mnie wkurza"
>
>No nie? :-)
>
>Maciek
Nie. Szukalem i nie znalazlem neistety. Widac zle szukalem...
A.L.
Maciek
> (....) Szukalem i nie znalazlem neistety. Widac zle szukalem...
>
No to kilka podpowiedzi (moze i innym sie przydadza).
Do szukania w grupach dyskusyjnych Google ma osobna dzialke:
http://groups.google.pl/
alias
http://groups.google.com/
Jak kto chce od razu ogladac grupy polskie, to:
http://www.google.pl/groups?group=pl
Niektore szczegolne frazy filtrujace zakres wyszukiwania:
author:maciek - szuka wiadomosci z wyrazem 'maciek' w polu nadawcy;
nie musi to byc jedyne slowo - 'Maciek Iksinski' tez sie zalapie
author:skrzynka...@serwer.poczty.pl - szuka wiadomosci wedlug
adresu pocztowego nadawcy; UWAGA: ten filtr musi byc DOKLADNY,
z pelna nazwa domenowa i ewentualnymi pulapkami na spam;
wyszukiwanie po czesci adresu nie zadziala
insubject:numer - szuka wiadomosci z wyrazem 'numer' w tytule
insubject:"numer nie" - szuka wiadomosci, ktore maja w tytule oba
wyrazy: 'numer nie' - obok siebie, i w tej kolejnosci (byc moze
jednak przedzielone znakami przestankowymi)
msgid:bfl9ps$n1h$1...@szmaragd.futuro.pl - szuka wiadomosci o podanym
identyfikatorze; przydaje sie przy szukaniu wczesniejszych
czesci watku, gdy watek rozpadl sie wskutek zmiany tytulu
(w takim przypadku Google nie zauwaza ciaglosci watku, pomimo
istnienia naglowka 'References')
group:pl.sci.matematyka - szuka wiadomosci wyslanych do wskazanej
grupy; mozna uzyc gwiazdki do oznaczenia calej hierarchii grup:
group:pl.sci.*
Warunki podane razem wyszukiwarka uwaza za koniunkcje:
insubject:numer insubject:nie group:pl.comp.* - szuka wiadomosci,
ktore maja w tytule oba wyrazy: 'numer' i 'nie' (chociaz
niekoniecznie obok siebie, i niekoniecznie w tej kolejnosci)
i zostaly wyslane do (dowolnej) grupy w hierarchii pl.comp.
Warunki polaczone wyrazem OR tworza prosta alternatywe, np.
group:pl.sci.matematyka OR group:pl.sci.fizyka
Wszystkie te (i inne jeszcze) opcje dostepne sa
w wygodnej postaci w formularzu:
http://www.google.pl/advanced_group_search
Mozna do niego trafic ze stron wskazanych na poczatku, korzystajac
z odsylacza "Zaawansowane Wyszukiwanie w Grupach Dyskusyjnych"
(w wersji angielskiej: "Advanced Groups Search").
HTH :-)
Maciek