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:
Use um algoritmo de classificação codificado manualmente que funcione para classificar listas de comprimento 5. Isso provavelmente é mais rápido que a função de biblioteca que você está usando no momento.
Não entendo por que você diz "O tipo não é simples" . A classificação é simples - converta cada cartão em um número de 1 a 52, para que a mão seja representada por uma lista (de comprimento 5) de cartões. Classifique essa lista. Esse é apenas o problema de classificar uma lista de 5 números inteiros, o que pode ser feito muito rapidamente, como Yuval menciona. Sugiro que você meça antes de assumir que é muito lento, mas meu palpite é que a classificação dessa lista será muito rápida e pode até ser mais rápida do que uma leitura de memória de acesso aleatório que não atinja o cache.
@dw Sim, o tipo é simples, mas o que estou fazendo (milhões de vezes) é simples. Eu testei e uma espécie dobra o tempo.
@Paparazzi Não, Yuval está dizendo para você escrever sua própria rotina de classificação, especificamente ajustada para classificar cinco números entre 1 e 52. Você tentou usar uma rotina de biblioteca, que é lenta porque é muito mais geral do que isso e porque a natureza recursiva O quicksort o torna muito ineficiente em listas curtas.
Na prática, a maioria dos itens que não são <= 16 bits também pode ter 32 bits. Portanto, como você precisa de pelo menos 23 bits, qualquer codificação que use <= 32 bits é provavelmente viável. A codificação trivial de 6 bits por cartão * 5 funciona bem o suficiente. Há uma ressalva: um índice de matriz de 23 bits é muito melhor que um índice de matriz de 32 bits.
CC[52,25,11][52,25,11]CC27×5227×5211115252A1,…,A52A1,…,A52AiAi272711101000a,b,c,d,ea,b,c,d,eAa⊕Ab⊕Ac⊕Ad⊕AeAa⊕Ab⊕Ac⊕Ad⊕Ae⊕⊕H1,H2H1,H210−2|H1∩H2|≤1010−2|H1∩H2|≤10
Bob Jenkins descreve esse código em seu site e, a partir disso, podemos extrair a matriz
252−27−1=225−1252−27−1=225−1
Eu não sigo exatamente. Quantos bits isso precisa para uma mão?
Precisa de 27 bits. Você pode usar qualquer número maior de bits.
— Yuval Filmus 06/04
Obrigado. Eu testei e os números são únicos e <= 32 bits. Posso derivar os 5 cartões do número? Se não estiver bem, basta perguntar.
Sim, é simples álgebra linear. Você pode usar a matriz correta para recuperar um vetor de comprimento 52 com 5. Eu vou deixar você descobrir isso.
nn⌈lgn⌉⌈lg⁡n⌉⌈lg2598960⌉=22⌈lg⁡2598960⌉=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:
Lado leste, lado oeste . Notas da palestra, Herbert S. Wilf, 14 de agosto de 1999. Seções 3.7-3.8.
/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.
Vou atualizar a pergunta. Sim, existem 2598960 mãos. O dicionário terá muitas linhas. Meu problema é a geração da chave. Em 5 cartões, preciso gerar uma chave para realizar a pesquisa no dicionário.
@Paparazzi, se você usar a abordagem de dicionário, a mão é a chave. Em outras palavras, a chave é a 5-tupla das cartas na mão (em ordem classificada). O dicionário pode ser armazenado como uma hashtable usando-o como chave. Se você não gosta dos custos de memória de um dicionário, use a abordagem alternativa: classificação / não classificação.
Sim, eu sei que posso obter a chave de 30 bits se eu classificar. Gostaria de saber se existe uma maneira de obter a chave de 32 bits ou menos sem classificar a tupla de 5 placas. Vou olhar para classificação e classificação.
Eu não sigo a classificação / classificação, mas obrigado. Vou tentar descobrir. Também tem as possibilidades de laços. Há muitos laços.
Também relevante: cs.stackexchange.com/questions/67664/…
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.
Isso usa 52 bits?
@Paparazzi, não. Dê uma outra olhada no último parágrafo. Eu o editei para tentar fornecer uma clareza ainda maior.