Représenter une main de poker à 5 cartes

Un jeu de cartes est 52. Une main est 5 cartes des 52 (ne peut pas avoir de doublon).

Quel est le moins de bits pour représenter une main de 5 cartes et comment?
Une main NE dépend PAS de l'ordre (KQ = QK). 64329 = 96432

Oui, peut utiliser 52 bits. Cela peut représenter une main de n'importe quel nombre de cartes.

Étant donné qu'une main représente exactement 5 cartes, existe-t-il un moyen de la représenter avec moins de 52 bits.

Une seule carte peut être représentée avec 6 bits = 64. Il pourrait donc simplement utiliser 6 bits * 5 cartes = 30 bits. Mais cela dépendrait de l'ordre. Je pourrais simplement trier et cela devrait fonctionner. Si cela ne fonctionne pas, faites-le moi savoir.

Existe-t-il un moyen d'obtenir la clé à 32 bits ou moins et de ne pas avoir à trier le tuple à 5 cartes.

C'est pour les simulations de poker et le tri serait beaucoup plus lourd que de simplement générer la main. Si j'ai un dictionnaire avec la valeur relative de chaque main, il s'agit de deux recherches simples et d'une comparaison pour comparer la valeur de deux mains. Si je dois d'abord trier les mains, c'est grand par rapport à deux recherches et une comparaison. Dans une simulation va comparer des millions. Je n'obtiendrai pas les mains triées de la simulation. Le tri n'est pas simple comme 52 51 50 49 48 avant 52 51 50 49 47. Vous pouvez avoir des quads affleurants droits ....

Il y a 2598960 mains de 5 cartes possibles. C'est le nombre de lignes. La clé est les 5 cartes. Je voudrais obtenir une clé de 32 bits ou moins où les cartes n'ont pas besoin d'être triées en premier.

Ne peut pas simplement commander la liste car de nombreuses mains sont nouées. Le costume est la pelle, le club, le diamant et le cœur. 7c 8c 2d 3d 4s = 7s 8s 2c 3c 4h. Il y a un grand nombre de liens.

La prochaine étape est de 64 bits et prendra le coup du tri plutôt que de doubler la taille de la clé.

J'ai testé et SortedSet<int> quickSort = new SortedSet<int>() { i, j, k, m, n };double le temps de l'opération mais je peux quand même le faire.

Cela devient plus complexe. J'ai besoin de pouvoir représenter un bateau à deux sur cinq (22255). Donc, les trier les rompt. Je sais que tu vas dire mais c'est rapide. Oui c'est rapide et trivial mais j'ai besoin le plus vite possible.

C # pour la réponse acceptée:

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("");
}

Soit un code . La matrice de contrôle de parité de est une matrice de bits telle que le nombre minimal de colonnes dont le XOR disparaît est de . Désignons les colonnes par . Nous pouvons identifier chaque comme un nombre binaire de longueur bits. La promesse est que le XOR de à de ces nombres n'est jamais . En utilisant cela, vous pouvez encoder votre main comme , où$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$est XOR. En effet, cela ne dépend clairement pas de l'ordre, et si deux mains entrent en collision, alors XOR les deux valeurs de hachage donnent nombres dont le XOR est zéro.$H_1,H_2$$10-2|H_1 \cap H_2|\leq 10$

Bob Jenkins décrit un tel code dans son site , et à partir de là, nous pouvons extraire le tableau

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

Comme les 27 premiers vecteurs ne sont que les 27 nombres de poids de Hamming 1, pour vérifier que cette construction est correcte, il suffit de considérer tous les possibles non triviaux combinaisons des 25 derniers nombres, en vérifiant que leurs XOR ont toujours un poids de Hamming d'au moins 10. Par exemple, le tout premier numéro 0x07fe0000 a un poids de Hamming exactement 10.$2^{52-27}-1 = 2^{25}-1$

Si nous avons un ensemble de taille , vous pouvez représenter un élément de l'ensemble en utilisant les . Vous dites qu'il y a 2598960 mains possibles de 5 cartes. Cela signifie qu'une main de 5 cartes peut être représentée en utilisant simplement bits. 22 bits est nettement plus court que 30 bits.⌈ lg n ⌉ ⌈ lg 2598960 ⌉ = $n$$\lceil \lg n \rceil$$\lceil \lg 2598960 \rceil = 22$

Comment fonctionne la représentation? Il existe différentes options, avec différents compromis. J'en énumère deux ci-dessous.

Dictionnaire codé en dur

Dans ce cas, le nombre de mains possibles de 5 cartes est suffisamment petit pour que vous puissiez avoir un dictionnaire codé en dur qui répertorie toutes les 2598960 mains, et vous représentez une main par son index dans le dictionnaire (représenté en binaire).

En d'autres termes, le dictionnaire peut être une liste triée de mains. Chaque main est le 5-tuple des cartes dans la main, dans l'ordre trié. Vous pouvez rechercher une main dans le dictionnaire en utilisant la recherche binaire et trouver son index correspondant; et étant donné un index, vous pouvez trouver la main correspondante. Ou, vous pouvez stocker le dictionnaire sous la forme d'une table de hachage qui correspond de la main à son index. L'index est un entier compris entre 0 et 2598959, il peut donc être représenté à l'aide de 23 bits.

Cette approche fonctionnera et sera très simple à programmer, mais elle gaspille de l'espace (taille de l'exécutable du programme).

Classement / non classé

Alternativement, si vous vous souciez, il existe de meilleures méthodes. Voir, par exemple, l'une des références suivantes:

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

• Côté est, côté ouest . Notes de cours, Herbert S. Wilf, 14 août 1999. Sections 3.7-3.8.

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

• /programming//q/3143142/781723

Le thème général est appelé "classement (et non classement) des combinaisons". Ceux-ci sont un peu plus complexes à implémenter et à comprendre, mais évitent d'avoir à inclure un dictionnaire codé en dur dans le programme.

Vous pouvez trier les cinq éléments et vérifier simultanément les doublons sans aucune comparaison sur certains processeurs: supposons qu'un processeur dispose d'une instruction rapide qui détermine la position du jeu de bits le plus élevé et d'une instruction rapide calculant un nombre avec uniquement le nième jeu de bits .

Soit bit (n) le nombre avec exactement le nième ensemble de bits. Soit bit_haut (x) le numéro du bit le plus haut défini dans le numéro x, avec une valeur non spécifiée si x = 0. Soit x ^ y l'exclusivité ou x et y.

Donné sont cinq nombres a, b, c, d et e, chacun de 0 à 51, représentant les cinq cartes dans la main.

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

Soit A = le plus haut_bit (x), changez x en x ^ bit (A).

Soit B = le plus haut_bit (x), changez x en x ^ bit (B).

Soit C = le plus haut_bit (x), changez x en x ^ bit (C).

Soit D = le plus haut_bit (x), changez x en x ^ bit (D).

Soit E = le plus haut_bit (x).

Si x = 0, il y avait des doublons dans les nombres a, b, c, d et e. Sinon, utilisez A * bit (24) + B * bit (18) + C * bit (12) + D * bit (6) + E comme encodage de la main, où A, B, C, D et E sont défini comme ci-dessus. Cela encode une main sous la forme d'une chaîne de 30 bits, tout en effectuant le tri de manière très efficace.