Hejka. Jestem w trakcie pisania programu, który coś tam (nieistotne dla
przedstawianego tu problemu) będzie liczył. Dziedzina - gry karciane.
Interesują mnie wszystkie możliwe kombinacje 5-elementowe ze zbioru
52-elemntowego (kolejność elementów wewnątrz kombinacji nie ma
znaczenia). C(52,5) = 2 598 960. Robię tablicę z tyloma wierszami i dla
każdej kombinacji umieszczam w niej jakieś dane. Tablica jest, dane są,
teraz potrzebuję dla losowo wygenerowanej kombinacji szybko odnaleźć
odpowiadający jej wiersz. I tu jest problem. Ze względu na to, co
program ma dalej liczyć i jakie operacje przeprowadzać, formatem tej
kombinacji jest liczba 52-bitowa z ustawionymi 5-ma bitami. Tablica w
której szukamy indeksowana jest 22-bitową wartością. W wyniku poszukiwań
jak to ugryźć wyszło mi hasło "funkcja haszująca/skrótu". Dla
przedstawionego problemu nieskuteczne jest: (kombinacje na 52 bitach)
mod (C52,5). Daje dużo powtórzeń. Czy ktoś z Was posiada wiedzę w jaki
sposób buduje się funkcję dla tej klasy problemów i mógł by się wiedzą
podzielić bądź naprowadzić ?

Pozdrawiam

do góry

No dobra, a dlaczego nie możesz posługiwać się piątką liczb 1..52
i potraktować je jako cyfry dla systemu liczenia o podstawie 52?
Wtedy miałbyś od razu indeks do tablicy, kosztem 5 mnożeń i 4 dodawań.

Jeśli to jednak nie przejdzie, to może lepiej rozważ użycie drzew
trie.

w.

do góry

W dniu 2013-09-23 22:35, Wojciech Muła pisze:

> No dobra, a dlaczego nie możesz posługiwać się piątką liczb 1..52
> i potraktować je jako cyfry dla systemu liczenia o podstawie 52?
> Wtedy miałbyś od razu indeks do tablicy, kosztem 5 mnożeń i 4 dodawań.

Przypuszczam, z powodem jest 52^5 = 380204032, większe od 2,5 miliona.


> Jeśli to jednak nie przejdzie, to może lepiej rozważ użycie drzew
> trie.



Napisałem funkcję c2num, która wykonuje przekształcenie, o które pytał
autor wątku. W funkcji używane są współczynniki dwumianowe, które
oczywiście można stablicować zamiast liczyć za każdym razem.

Przykład (C) pokazuje przypadek dla n=6, k=2.





long long int bin2int(char *s)
{
long long int res = 0;
while(*s)
{ res = 2 * res + (*s=='1');
s++;
}
return res;
}

/* Współczynnik dwumianowy */
int binom(int n, int k)
{ if ((k==0) || (k==n)) return 1; else return binom(n-1,k-1)+binom(n-1,k); }


/* Wyznaczenie numeru kombinacji zapisanej w C jako ciąg zero-jedynkowy */
int c2num(int n, int k, long long int C)
{
int res;
long long int mask;
mask = 1;
res = 0;
while (k>0 && n>0)
{
n--;
if ((C & mask)==0) res += binom(n,k-1); else k--;
mask <<= 1;
}
return res;
}


int main()
{
printf ("%d\n",c2num(6,2,bin2int("000011")));
printf ("%d\n",c2num(6,2,bin2int("000101")));
printf ("%d\n",c2num(6,2,bin2int("001001")));
printf ("%d\n",c2num(6,2,bin2int("010001")));
printf ("%d\n",c2num(6,2,bin2int("100001")));
printf ("%d\n",c2num(6,2,bin2int("000110")));
printf ("%d\n",c2num(6,2,bin2int("001010")));
printf ("%d\n",c2num(6,2,bin2int("010010")));
printf ("%d\n",c2num(6,2,bin2int("100010")));
printf ("%d\n",c2num(6,2,bin2int("001100")));
printf ("%d\n",c2num(6,2,bin2int("010100")));
printf ("%d\n",c2num(6,2,bin2int("100100")));
printf ("%d\n",c2num(6,2,bin2int("011000")));
printf ("%d\n",c2num(6,2,bin2int("101000")));
printf ("%d\n",c2num(6,2,bin2int("110000")));
return 0;

}


Wynik:
0
1
2
3
4
5
...
14



P.

do góry

W dniu 2013-09-24 00:53, Piotrne pisze:
> W dniu 2013-09-23 22:35, Wojciech Muła pisze:
>
>> No dobra, a dlaczego nie możesz posługiwać się piątką liczb 1..52
>> i potraktować je jako cyfry dla systemu liczenia o podstawie 52?
>> Wtedy miałbyś od razu indeks do tablicy, kosztem 5 mnożeń i 4 dodawań.
>
> Przypuszczam, z powodem jest 52^5 = 380204032, większe od 2,5 miliona.
>
>
>> Jeśli to jednak nie przejdzie, to może lepiej rozważ użycie drzew
>> trie.
>
>
>
> Napisałem funkcję c2num, która wykonuje przekształcenie, o które pytał
> autor wątku. W funkcji używane są współczynniki dwumianowe, które
> oczywiście można stablicować zamiast liczyć za każdym razem.

Pytacz pewnie by docenił dwa słowa, skąd wzorek;)


Współczynniki pewnie rzeczywiście najłatwiej stablicować,
na pewno nie mogą zostać tak:

> /* Współczynnik dwumianowy */
> int binom(int n, int k)
> { if ((k==0) || (k==n)) return 1; else return
> binom(n-1,k-1)+binom(n-1,k); }

Odpalenie binom(n,k) oznacza odpalenie tej funkcji
rekurencyjnie C(n,k)*2-1 razy. Dla n=52 i k=26 to 9.9*10^14 razy.
:-)

Lepszym, a nadal prostym wzorkiem jest np 12 stąd:
http://mathworld.wolfram.com/BinomialCoefficient.htm
l
C(n; k+1) = ( C(n; k) * (n-k) ) / (k+1)
plus C(n;0)=1 oczywiście.


nawiązując do oryginalnego pytania:
Piotrne wykorzystał tutaj postać liczb. Nie zawsze się
tak da, Ale nawet, jeśli nasze liczby sa losowe nie wszytko
stracone, nadal możemy zbudować doskonałą funkcję haszującą,
kosztem oczywiście pamięci.

Date: Thu, 7 Mar 2013 19:10:04 -0800 (PST)
Message-ID: <3...@g...c
om>
Subject: w poszukiwaniu funkcji hash
i hasełko perfect hash.

Można też brutalniej. Zapisać wszystkie liczby 'pięciobinarne',
posortować, a potem indeksu szukać binarnie. Obstawiam jednak,
że wzorek będzie szybszy.

pzdr
bartekltg

do góry

W dniu 2013-09-24 06:06, bartekltg pisze:

> Pytacz pewnie by docenił dwa słowa, skąd wzorek;)


Wzorek jest spisany m.in. tu:
http://math.stackexchange.com/questions/349924/funct
ion-mapping-combinations-to-natural-numbers

Wyjaśnić go można obrazowo na trójkącie Pascala
ze współczynnikami dwumianowymi. Dla podanego
przykładu (kombinacje 2 elementów z 6) znajdujemy
liczbę C(6,2) = 15. Tyle jest różnych kombinacji.
Jednocześnie tyle jest różnych "dróg" prowadzących
od liczby 15 do jedynki na górze trójkąta - przyjmując,
że poruszamy się zawsze o "piętro" w górę (do n-1),
w lewo (do k-1) lub w prawo (do k). Każda spośród tych
dróg reprezentuje inną kombinację: element należy
do podzbioru, jeśli "skręciliśmy w lewo" (wybraliśmy k-1).

Pozostaje więc ponumerowanie dróg (i jednocześnie kombinacji).
Dla przykładowej 15 (= 5 + 10) przyjmujemy, że 5 początkowych
numerów (0 do 4) pochodzi z "piątki", a 10 kolejnych numerów
(5 do 14) z "dziesiątki". Przenosząc się o poziom wyżej:
numery 5 do 14 pochodzą z "czwórki" (5 do 8) oraz "szóstki"
(9 do 14). I tak dalej...


P.

do góry

Piotrne pisze:
> W dniu 2013-09-24 06:06, bartekltg pisze:
>
> > Pytacz pewnie by docenił dwa słowa, skąd wzorek;)
>
>
> Wzorek jest spisany m.in. tu:
> http://math.stackexchange.com/questions/349924/funct
ion-mapping-combinations-to-natural-numbers
>
>
> Wyjaśnić go można obrazowo na trójkącie Pascala
> ze współczynnikami dwumianowymi. Dla podanego
> przykładu (kombinacje 2 elementów z 6) znajdujemy
> liczbę C(6,2) = 15. Tyle jest różnych kombinacji.
> Jednocześnie tyle jest różnych "dróg" prowadzących
> od liczby 15 do jedynki na górze trójkąta - przyjmując,
> że poruszamy się zawsze o "piętro" w górę (do n-1),
> w lewo (do k-1) lub w prawo (do k). Każda spośród tych
> dróg reprezentuje inną kombinację: element należy
> do podzbioru, jeśli "skręciliśmy w lewo" (wybraliśmy k-1).
>
> Pozostaje więc ponumerowanie dróg (i jednocześnie kombinacji).
> Dla przykładowej 15 (= 5 + 10) przyjmujemy, że 5 początkowych
> numerów (0 do 4) pochodzi z "piątki", a 10 kolejnych numerów
> (5 do 14) z "dziesiątki". Przenosząc się o poziom wyżej:
> numery 5 do 14 pochodzą z "czwórki" (5 do 8) oraz "szóstki"
> (9 do 14). I tak dalej...

Dzięki za pomoc, algorytm działa idealnie na moich danych, choć to jak
działa nie do końca jeszcze rozumiem :) Współczynniki stablicowałem.
Uzupełniając jeszcze Twoją odpowiedź dla Wojtka, dlaczego nie liczby w
systemie 52. Tak (w sensie - bitowo)zakodowane kombinacje można łatwo
testować na okoliczność zawierania lub nie elementów przy pomocy
operatorów bitowych. Ma to znaczenie gdy podzbiór który obrabiam jest
zdefiniowany w taki sposób, że generowanie iteracyjne jedynie
prawidłowych kombinacji jest skomplikowane i raczej mało efektywne.
Przykład:
Tu muszę nadmienić, że tablica do której robiliśmy wskazania, jest tylko
przejściową do innej, posortowanej wg. takiego klucza, który gwarantuje
(poza przypadkami szczególnymi), że podzbiory które będziemy badać będą
w niej ciągłe (wszystkie wartości od indeksu a do b). Wracając o
przykładu - odniosę się do faktycznych danych. Mamy zbadać coś we
wszystkich kombinacjach par od QQxxx do AAxxx, przy czym w xxx nie może
być kilku konkretnych kart. Ponieważ mają to być pary, generując
iteracyjnie musiał bym zadbać by xxx oprócz kart których nie mogą z
założenia zawierać, nie zawierały w sobie róznych innych tworów typu np.
55x, które z jednej pary tworzą dwie pary. Natomiast jeśli wyjdę od
strony tablicy w której pary AA-QQ są w ciągłym zakresie indeksów i nie
ma wśród nich kart klasy innej niż para (tak jest posortowana tablica)
wówczas pozostaje mi zbadać tylko jawnie zadane warunki nie zawierania
konkretnych kart. Przy bitowym zakodowaniu robię to najczęściej jednym
AND, przy kodowaniu w systemie 52 muszę się gimnastykować.

Pozdrawiam

do góry

On 2013-09-23 21:46, Przemysłąw Dębski wrote:
>
> Hejka. Jestem w trakcie pisania programu, który coś tam (nieistotne dla
> przedstawianego tu problemu) będzie liczył. Dziedzina - gry karciane.
A co tworzysz, jeśli to nie tajemnica? Bo jeśli potrzebujesz hand
evaluator-a to gotowy jest tutaj: http://gna.org/projects/pokersource/.

do góry

W dniu środa, 25 września 2013 12:36:16 UTC+2 użytkownik JDX napisał:
> On 2013-09-23 21:46, Przemysłąw Dębski wrote:
>
> >
>
> > Hejka. Jestem w trakcie pisania programu, który coś tam (nieistotne dla
>
> > przedstawianego tu problemu) będzie liczył. Dziedzina - gry karciane.
>
> A co tworzysz, jeśli to nie tajemnica? Bo jeśli potrzebujesz hand
>
> evaluator-a to gotowy jest tutaj: http://gna.org/projects/pokersource/.

Dokładnie - evaluator, jednak dla bardzo niszowej współcześnie odmiany "5 card draw".
Dla tej odmiany spotkałem się z jednym narzędziem (SlicEV), który potrafi co prawda
policzyć coś na zakresach, ale nie uwzględnia że w tej odmianie karty się wymienia :)
Można jeszcze używać kalkulatorów do odmiany "2-7 Lowaball", 1-wynik który on
pokazuje jest przybliżeniem wyniku dla 5-card draw. W obydwu narzędziach nie ma
możliwości zdefiniowania zakresu z drawami.
U mnie ma to być (w zasadzie już jest - jeszcze co prawda program nic nie liczy, ale
drawy i drawy z parami rozróżnia), plus dodatkowo dla każdej ręki/zakresu w danej
kategorii można będzie ustawiać różne strategie wymiany kart u przeciwnika.
Przykładowo będziemy chcieli obliczać equity naszej ręki vs jakiś calling range
np.pary 99-AA, to będziemy mogli uwzględnić że normalnie przeciwniki wymienia 3
karty, ale jeśli ma K lub A jako kickera wówczas go zostawi i wymieni 2.

Pozdrawiam

do góry

On 2013-09-25 15:05, p...@g...pl wrote:
[...]
> Dokładnie - evaluator, jednak dla bardzo niszowej współcześnie
> odmiany "5 card draw".
5CD sie nie zajmowałem, ale z tego co pamiętam, to w przykładach jest
tam taki programik "pokenum" który liczy equity m.in. dla 5CD (a także
dla lowball-i A5 i 27). Może to coś pomoże.

do góry

Użytkownik <p...@g...pl> napisał w wiadomości
news:a2996597-b514-41b5-9558-e713371d0679@googlegrou
ps.com...
W dniu środa, 25 września 2013 12:36:16 UTC+2 użytkownik JDX napisał:

>Dokładnie - evaluator

Widze, ze kolega coraz powazniej :-)

do góry