Representar uma mão de pôquer de 5 cartas

Um baralho de cartas é 52. Uma mão é 5 cartas dos 52 (não pode ter uma duplicata).

Qual é a menor quantidade de bits para representar uma mão de 5 cartas e como?
Uma mão NÃO depende da ordem (KQ = QK). 64329 = 96432

Sim, pode usar 52 bits. Isso pode representar uma mão de qualquer número de cartas.

Dada uma mão são exatamente 5 cartas, existe uma maneira de representá-la com menos de 52 bits.

Um único cartão pode ser representado com 6 bits = 64. Então, basta usar 6 bits * 5 cartões = 30 bits. Mas isso seria dependente da ordem. Eu poderia apenas classificar e isso deve funcionar. Se isso não funcionar, por favor me avise.

Existe uma maneira de obter a chave para 32 bits ou menos e não precisar classificar a tupla de 5 placas.

Isso é para simulações de pôquer e a classificação seria muito cara, em comparação com apenas gerar a mão. Se eu tenho um dicionário com o valor relativo de cada mão, são duas pesquisas simples e uma comparação para comparar o valor de duas mãos. Se eu tiver que classificar as mãos primeiro, é grande em comparação com duas pesquisas e uma comparação. Em uma simulação irá comparar milhões. Não receberei as mãos classificadas da simulação. A classificação não é simples como 52 51 50 49 48 antes de 52 51 50 49 47. Você pode ter quads de straight flush ....

Existem 2598960 possíveis 5 mãos para cartas. Esse é o número de linhas. A chave são os 5 cartões. Eu gostaria de obter uma chave de 32 bits ou abaixo de onde os cartões não precisam ser classificados primeiro.

Não é possível apenas solicitar a lista, pois há muitas mãos amarradas. Naipe são pá, taco, diamante e coração. 7c 8c 2d 3d 4s = 7s 8s 2c 3c 4h. Há um grande número de laços.

O próximo passo é de 64 bits e receberá o resultado da classificação em vez de dobrar o tamanho da chave.

Eu testei e SortedSet<int> quickSort = new SortedSet<int>() { i, j, k, m, n };dobra o tempo da operação, mas ainda posso fazê-lo.

Fica mais complexo. Eu preciso ser capaz de representar um barco de dois em cinco (22255). Então, classificá-los quebra isso. Eu sei que você vai dizer, mas isso é rápido. Sim, é rápido e trivial, mas eu preciso o mais rápido possível.

C # para a resposta aceita:

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 descreve esse código em seu site e, a partir disso, podemos extrair a 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$

Como funciona a representação? Existem várias opções, com diferentes trocas. Listo dois abaixo.

Dicionário codificado

Nesse caso, o número possível de mãos com 5 cartas é pequeno o suficiente para que você possa ter um dicionário codificado que lista todas as 2598960 mãos e você representa uma mão por seu índice no dicionário (representado em binário).

Em outras palavras, o dicionário pode ser uma lista ordenada de mãos. Cada mão é a 5-tupla das cartas na mão, em ordem ordenada. Você pode procurar uma mão no dicionário usando a pesquisa binária e encontrar seu índice correspondente; e com um índice, você pode encontrar a mão correspondente. Ou você pode armazenar o dicionário como um mapa de hash que mapeia da mão para seu índice. O índice é um número inteiro entre 0 e 2598959, portanto, pode ser representado usando 23 bits.

Essa abordagem funcionará e será muito simples de programar, mas é um desperdício de espaço (tamanho do programa executável).

Classificação / desagregação

Como alternativa, se você se importa, existem métodos melhores. Veja, por exemplo, qualquer uma das seguintes referências:

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

• Lado leste, lado oeste . Notas da palestra, Herbert S. Wilf, 14 de agosto de 1999. Seções 3.7-3.8.

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

• /programming//q/3143142/781723

O tópico geral é conhecido como "classificação (e sem classificação) de combinações". Eles são um pouco mais complexos de implementar e entender, mas evitam a necessidade de incluir um dicionário codificado no programa.

Você pode classificar os cinco itens e verificar se há duplicatas simultaneamente, sem nenhuma comparação em alguns processadores: Suponha que um processador tenha uma instrução rápida que determina a posição do conjunto de bits mais alto e uma instrução rápida calculando um número apenas com o conjunto de n-ésimos bits .

Seja bit (n) o número exatamente com o n-ésimo bit definido. Seja o mais alto bit (x) o número do bit mais alto definido no número x, com um valor não especificado se x = 0. Seja x ^ y o exclusivo ou de x e y.

Dado são cinco números a, b, c, d e e, cada um de 0 a 51, representando as cinco cartas na mão.

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

Seja A = maior_bit (x), altere x para x ^ bit (A).

Seja B = maior_bit (x), altere x para x ^ bit (B).

Seja C = maior_bit (x), altere x para x ^ bit (C).

Seja D = maior_bit (x), altere x para x ^ bit (D).

Seja E = maior_bit (x).

Se x = 0, havia duplicatas nos números a, b, c, d e e. Caso contrário, use A * bit (24) + B * bit (18) + C * bit (12) + D * bit (6) + E como a codificação da mão, onde A, B, C, D e E são definido como acima. Isso codifica uma mão como uma string de 30 bits, enquanto faz a classificação de uma maneira muito eficiente.