Representa una mano de póker de 5 cartas

Una baraja de cartas es 52. Una mano está a 5 cartas de las 52 (no puede tener un duplicado).

¿Cuál es la menor cantidad de bits para representar una mano de 5 cartas y cómo?
Una mano NO depende del orden (KQ = QK). 64329 = 96432

Sí, puede usar 52 bits. Eso puede representar una mano de cualquier cantidad de cartas.

Dada una mano es exactamente 5 cartas, ¿hay alguna manera de representarla con menos de 52 bits?

Una sola tarjeta se puede representar con 6 bits = 64. Por lo tanto, podría usar solo 6 bits * 5 tarjetas = 30 bits. Pero eso dependería del orden. Podría ordenar y esto debería funcionar. Si eso no funciona, por favor hágamelo saber.

¿Hay alguna manera de obtener la clave de 32 bits o menos y no tener que ordenar la tupla de 5 tarjetas?

Esto es para simulaciones de póquer y la clasificación supondría una gran sobrecarga en comparación con solo generar la mano. Si tengo un diccionario con el valor relativo de cada mano, son dos búsquedas simples y una comparación para comparar el valor de dos manos. Si tengo que ordenar las manos primero, eso es grande en comparación con dos búsquedas y una comparación. En una simulación comparará millones. No obtendré manos ordenadas de la simulación. El tipo no es simple como 52 51 50 49 48 antes de 52 51 50 49 47. Puede tener quads de descarga recta ...

Hay 2598960 posibles 5 manos de cartas. Ese es el número de filas. La clave son las 5 cartas. Me gustaría obtener una clave de 32 bits o menos donde las tarjetas no necesitan ser ordenadas primero.

No se puede simplemente ordenar la lista con tantas manos atadas. Los trajes son pala, garrote, diamante y corazón. 7c 8c 2d 3d 4s = 7s 8s 2c 3c 4h. Hay una gran cantidad de lazos.

El siguiente paso es de 64 bits y recibirá el golpe del tipo en lugar de duplicar el tamaño de la clave.

Probé y SortedSet<int> quickSort = new SortedSet<int>() { i, j, k, m, n };doblé el tiempo de la operación, pero aún puedo hacerlo.

Se vuelve más complejo. Necesito poder representar un barco como dos sobre cinco (22255). Entonces ordenarlos rompe eso. Sé que lo vas a decir, pero eso es rápido. Sí, es rápido y trivial, pero necesito lo más rápido posible.

C # para la respuesta aceptada:

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 describe dicho código en su sitio , y de eso podemos extraer la matriz

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$

¿Cómo funciona la representación? Hay varias opciones, con diferentes compensaciones. Enumero dos a continuación.

Diccionario codificado

En este caso, el número de manos posibles de 5 cartas es lo suficientemente pequeño como para que pueda tener un diccionario codificado que enumere todas las manos 2598960, y represente una mano por su índice en el diccionario (representado en binario).

En otras palabras, el diccionario puede ser una lista ordenada de manos. Cada mano es la 5-tupla de las cartas en la mano, en orden ordenado. Puede buscar una mano en el diccionario utilizando la búsqueda binaria y encontrar su índice correspondiente; y dado un índice, puedes encontrar la mano correspondiente. O bien, puede almacenar el diccionario como un hashmap que se asigna de la mano a su índice. El índice es un número entero entre 0 y 2598959, por lo que se puede representar con 23 bits.

Este enfoque funcionará y será muy simple de programar, pero es un desperdicio de espacio (tamaño del programa ejecutable).

Clasificación / clasificación

Alternativamente, si te importa, hay mejores métodos. Ver, por ejemplo, cualquiera de las siguientes referencias:

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

• East Side, West Side . Notas de la conferencia, Herbert S. Wilf, 14 de agosto de 1999. Secciones 3.7-3.8.

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

• /programming//q/3143142/781723

El tema general se conoce como "clasificación (y clasificación) de combinaciones". Estos son un poco más complejos de implementar y comprender, pero evite la necesidad de incluir un diccionario codificado en el programa.

Puede ordenar los cinco elementos y verificar simultáneamente si hay duplicados sin ninguna comparación en algunos procesadores: suponga que un procesador tiene una instrucción rápida que determina la posición del conjunto de bits más alto y una instrucción rápida que calcula un número con solo el enésimo conjunto de bits .

Deje que el bit (n) sea el número con exactamente el enésimo conjunto de bits. Sea el más alto_bit (x) el número del bit más alto que se establece en el número x, con un valor no especificado si x = 0. Sea x ^ y el exclusivo-o de x e y.

Se dan cinco números a, b, c, d y e, cada uno del 0 al 51, que representan las cinco cartas en la mano.

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

Deje A = mayor_bit (x), cambie x a x ^ bit (A).

Deje B = el más alto_bit (x), cambie x a x ^ bit (B).

Deje C = el más alto_bit (x), cambie x a x ^ bit (C).

Deje D = el más alto_bit (x), cambie x a x ^ bit (D).

Deje E = el más alto_bit (x).

Si x = 0, entonces había duplicados en los números a, b, c, d, y e. De lo contrario, use A * bit (24) + B * bit (18) + C * bit (12) + D * bit (6) + E como codificación de la mano, donde A, B, C, D y E son definido como arriba. Esto codifica una mano como una cadena de 30 bits, mientras realiza la clasificación de una manera muy eficiente.