Reprezentuj układ 5 kart

Talia kart to 52. Ręka to 5 kart z 52 (nie może mieć duplikatu).

Jaka jest najmniejsza liczba bitów reprezentująca układ 5 kart i jak?
Ręka NIE jest zależna od kolejności (KQ = QK). 64329 = 96432

Tak, można użyć 52 bitów. Może to stanowić układ dowolnej liczby kart.

Biorąc pod uwagę, że ręka ma dokładnie 5 kart, istnieje sposób, aby przedstawić ją za pomocą mniej niż 52 bitów.

Pojedyncza karta może być reprezentowana przez 6 bitów = 64. Więc może po prostu użyć 6 bitów * 5 kart = 30 bitów. Ale to zależy od porządku. Mógłbym po prostu posortować i to powinno działać. Jeśli to nie zadziała, daj mi znać.

Czy istnieje sposób, aby uzyskać klucz do 32 bitów lub mniej i nie trzeba sortować krotki 5 kart.

Dotyczy to symulacji pokera, a sortowanie byłoby narzutem w porównaniu z samym generowaniem ręki. Jeśli mam słownik ze względną wartością każdej ręki, to są to dwa proste wyszukiwania i porównanie w celu porównania wartości dwóch rąk. Jeśli najpierw muszę posortować ręce, które są duże w porównaniu do dwóch wyszukiwań i porównania. W symulacji porówna miliony. Nie otrzymam posortowanych rąk z symulacji. Sortowanie nie jest proste, jak 52 51 50 49 48 przed 52 51 50 49 47. Możesz mieć quady z równymi kolorami ....

Istnieje 2598960 możliwych 5 kart. To jest liczba rzędów. Kluczem jest 5 kart. Chciałbym uzyskać klucz o długości 32 bitów lub mniejszy, w którym karty nie muszą być najpierw sortowane.

Nie można tak po prostu zamówić listy, gdy wiąże się wiele rąk. Kolor to szpadel, kij, diament i serce. 7c 8c 2d 3d 4s = 7s 8s 2c 3c 4h. Istnieje duża liczba więzi.

Kolejny krok to 64 bity i będzie to taki hit, a nie dwukrotność wielkości klucza.

Testowałem i SortedSet<int> quickSort = new SortedSet<int>() { i, j, k, m, n };podwajam czas operacji, ale nadal mogę to zrobić.

Staje się bardziej złożony. Muszę być w stanie przedstawić łódź jako dwójkę nad piątką (22255). Sortowanie ich psuje to. Wiem, że masz zamiar powiedzieć, ale to jest szybkie. Tak, jest szybki i trywialny, ale potrzebuję tak szybko, jak to możliwe.

C # dla zaakceptowanej odpowiedzi:

private int[] DeckXOR = new int[] {0x00000001,0x00000002,0x00000004,0x00000008,0x00000010,0x00000020,0x00000040,
                                    0x00000080,0x00000100,0x00000200,0x00000400,0x00000800,0x00001000,0x00002000,
                                    0x00004000,0x00008000,0x00010000,0x00020000,0x00040000,0x00080000,0x00100000,
                                    0x00200000,0x00400000,0x00800000,0x01000000,0x02000000,0x04000000,0x07fe0000,
                                    0x07c1f000,0x0639cc00,0x01b5aa00,0x056b5600,0x04ed6900,0x039ad500,0x0717c280,
                                    0x049b9240,0x00dd0cc0,0x06c823c0,0x07a3ef20,0x002a72e0,0x01191f10,0x02c55870,
                                    0x007bbe88,0x05f1b668,0x07a23418,0x0569d998,0x032ade38,0x03cde534,0x060c076a,
                                    0x04878b06,0x069b3c05,0x054089a3};
public void PokerProB()
{
    Stopwatch sw = new Stopwatch();
    sw.Start();
    HashSet<int> cardsXOR = new HashSet<int>();
    int cardXOR;
    int counter = 0;
    for (int i = 51; i >= 4; i--)
    {
        for (int j = i - 1; j >= 3; j--)
        {
            for (int k = j - 1; k >= 2; k--)
            {
                for (int m = k - 1; m >= 1; m--)
                {
                    for (int n = m - 1; n >= 0; n--)
                    {
                        counter++;
                        cardXOR = DeckXOR[i] ^ DeckXOR[j] ^ DeckXOR[k] ^ DeckXOR[m] ^ DeckXOR[n];
                        if (!cardsXOR.Add(cardXOR))
                            Debug.WriteLine("problem");
                    }
                }
            }
        }
    }
    sw.Stop();
    Debug.WriteLine("Count {0} millisec {1} ", counter.ToString("N0"), sw.ElapsedMilliseconds.ToString("N0"));
    Debug.WriteLine("");
}

$C$$[52,25,11]$$C$$27 \times 52$$11$$52$$A_1,\ldots,A_{52}$$A_i$$27$$1$$10$$0$$a,b,c,d,e$$A_a \oplus A_b \oplus A_c \oplus A_d \oplus A_e$$\oplus$$H_1,H_2$$10-2|H_1 \cap H_2|\leq 10$

Bob Jenkins opisuje taki kod na swojej stronie , z której możemy wyodrębnić tablicę

0x00000001,0x00000002,0x00000004,0x00000008,0x00000010,0x00000020,0x00000040,
0x00000080,0x00000100,0x00000200,0x00000400,0x00000800,0x00001000,0x00002000,
0x00004000,0x00008000,0x00010000,0x00020000,0x00040000,0x00080000,0x00100000,
0x00200000,0x00400000,0x00800000,0x01000000,0x02000000,0x04000000,0x07fe0000,
0x07c1f000,0x0639cc00,0x01b5aa00,0x056b5600,0x04ed6900,0x039ad500,0x0717c280,
0x049b9240,0x00dd0cc0,0x06c823c0,0x07a3ef20,0x002a72e0,0x01191f10,0x02c55870,
0x007bbe88,0x05f1b668,0x07a23418,0x0569d998,0x032ade38,0x03cde534,0x060c076a,
0x04878b06,0x069b3c05,0x054089a3

$2^{52-27}-1 = 2^{25}-1$

$n$$\lceil \lg n \rceil$$\lceil \lg 2598960 \rceil = 22$

Jak działa reprezentacja? Istnieją różne opcje, z różnymi kompromisami. Wymieniam dwa poniżej.

Słownik na stałe

W tym przypadku liczba możliwych układów 5-kartowych jest na tyle mała, że ​​można mieć tylko zakodowany słownik, który zawiera listę wszystkich 2598960 układów, a ty reprezentujesz układ według jego indeksu w słowniku (reprezentowanego w postaci binarnej).

Innymi słowy, słownik może być posortowaną listą rąk. Każda ręka to 5 krotek kart w ręce, w posortowanej kolejności. Możesz wyszukać dłoń w słowniku za pomocą wyszukiwania binarnego i znaleźć odpowiedni indeks; i biorąc pod uwagę indeks, możesz znaleźć odpowiednią rękę. Lub możesz zapisać słownik jako mapę skrótową, która mapuje od ręki do jej indeksu. Indeks jest liczbą całkowitą od 0 do 2598959, więc można go przedstawić za pomocą 23 bitów.

Takie podejście będzie działać i będzie bardzo proste do zaprogramowania, ale jest marnotrawstwem przestrzeni (rozmiar pliku wykonywalnego programu).

Ranking / nieranking

Alternatywnie, jeśli cię to obchodzi, istnieją lepsze metody. Zobacz np. Dowolne z następujących odniesień:

• https://en.wikipedia.org/wiki/Combinatorial_number_system

• East Side, West Side . Notatki z wykładu, Herbert S. Wilf, 14 sierpnia 1999 r. Sekcje 3.7-3.8.

• https://computationalcombinatorics.wordpress.com/2012/09/10/ranking-and-unranking-of-combinations-and-permutations/

• https://stackoverflow.com/q/3143142/781723

Ogólny temat jest znany jako „ranking (i nieranking) kombinacji”. Są one nieco bardziej skomplikowane w implementacji i zrozumieniu, ale unikają potrzeby dołączania do programu słownika zakodowanego na stałe.

Możesz sortować pięć elementów i jednocześnie sprawdzać duplikaty bez żadnych porównań na niektórych procesorach: Załóżmy, że procesor ma szybką instrukcję, która określa pozycję najwyższego zestawu bitów, oraz szybką instrukcję obliczającą liczbę tylko z n-tym zestawem bitów .

Niech bit (n) będzie liczbą z dokładnie n-tym bitem. Niech najwyższy_bit (x) będzie liczbą najwyższego bitu ustawionego w liczbie x, z nieokreśloną wartością, jeśli x = 0. Niech x ^ y będzie wyłącznością-lub z xiy.

Podano pięć liczb a, b, c, di e, każda od 0 do 51, reprezentujących pięć kart w ręce.

Niech x = bit (a) ^ bit (b) ^ bit (c) ^ bit (d) ^ bit (e).

Niech A = najwyższa_bit (x), zmień x na x ^ bit (A).

Niech B = najwyższy_bit (x), zmień x na x ^ bit (B).

Niech C = najwyższy_bit (x), zmień x na x ^ bit (C).

Niech D = najwyższy_bit (x), zmień x na x ^ bit (D).

Niech E = najwyższa_bit (x).

Jeśli x = 0, to były liczby w liczbach a, b, c, d i e. W przeciwnym razie użyj A * bit (24) + B * bit (18) + C * bit (12) + D * bit (6) + E jako kodowanie ręki, gdzie A, B, C, D i E to zdefiniowane jak powyżej. To koduje rękę jako 30-bitowy ciąg, a sortowanie odbywa się w bardzo wydajny sposób.