Stellen Sie eine 5-Karten-Pokerhand dar

Ein Kartenspiel ist 52. Eine Hand ist 5 Karten von den 52 (kann kein Duplikat haben).

Was ist die geringste Anzahl von Bits, um eine 5-Karten-Hand darzustellen, und wie?
Eine Hand ist NICHT auftragsabhängig (KQ = QK). 64329 = 96432

Ja, kann 52 Bit verwenden. Das kann eine Hand aus beliebig vielen Karten darstellen.

Wenn eine Hand genau 5 Karten hat, gibt es eine Möglichkeit, sie mit weniger als 52 Bit darzustellen.

Eine einzelne Karte kann mit 6 Bit = 64 dargestellt werden. Es können also nur 6 Bit * 5 Karten = 30 Bit verwendet werden. Das wäre aber auftragsabhängig. Ich könnte einfach sortieren und das sollte funktionieren. Wenn das nicht funktionieren würde, lass es mich wissen.

Gibt es eine Möglichkeit, den Schlüssel auf 32 Bit oder weniger zu bringen und das 5-Karten-Tupel nicht sortieren zu müssen?

Dies ist für Pokersimulationen gedacht und das Sortieren wäre viel Aufwand im Vergleich zum Generieren der Hand. Wenn ich ein Wörterbuch mit dem relativen Wert jeder Hand habe, sind es zwei einfache Suchvorgänge und ein Vergleich, um den Wert zweier Hände zu vergleichen. Wenn ich zuerst die Hände sortieren muss, ist das im Vergleich zu zwei Suchvorgängen und einem Vergleich groß. In einer Simulation werden Millionen verglichen. Ich werde keine sortierten Hände von der Simulation bekommen. Die Sortierung ist nicht einfach wie 52 51 50 49 48 vor 52 51 50 49 47. Sie können gerade bündige Quads haben ....

Es sind 2598960 5 Kartenhände möglich. Das ist die Anzahl der Zeilen. Der Schlüssel sind die 5 Karten. Ich möchte einen Schlüssel mit 32 Bit oder weniger erhalten, bei dem die Karten nicht zuerst sortiert werden müssen.

Kann nicht einfach die Liste bestellen, da viele Hände binden. Anzug sind Spaten, Keule, Diamant und Herz. 7c 8c 2d 3d 4s = 7s 8s 2c 3c 4h. Es gibt eine große Anzahl von Bindungen.

Der nächste Schritt ist 64 Bit und führt zu einem Treffer der Art, anstatt die Größe des Schlüssels zu verdoppeln.

Ich habe SortedSet<int> quickSort = new SortedSet<int>() { i, j, k, m, n };die Operationszeit getestet und verdoppelt, aber ich kann es trotzdem tun.

Es wird komplexer. Ich muss in der Lage sein, ein Boot zu zweit über fünf darzustellen (22255). Das Sortieren bricht das also. Ich weiß, dass du sagen wirst, aber das geht schnell. Ja, es ist schnell und trivial, aber ich brauche so schnell wie möglich.

C # für die akzeptierte Antwort:

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

Sei ein Code. Die Paritätsprüfmatrix von ist eine Bit-Matrix, so dass die minimale Anzahl von Spalten, deren XOR verschwindet, beträgt . Bezeichnen Sie die Spalten mit . Wir können jedes als eine Binärzahl mit einer Länge von Bit identifizieren . Das Versprechen ist, dass der XOR von bis dieser Zahlen niemals . Auf diese Weise können Sie Ihre Hand als , wobei[ 52 , 25 , 11 ] C 27 × 52 11 52 A 1 , … , A 52 A i 27 1 10 0 a , b , c , d , e A a ⊕ A b ⊕ A c ⊕ A d ⊕ A e ⊕ H 1 , H 2 10 - 2 $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$ist XOR. In der Tat hängt dies eindeutig nicht von der Reihenfolge ab, und wenn zwei Hände kollidieren, ergibt das XORing der beiden Hash-Werte Zahlen, deren XOR Null ist.$H_1,H_2$$10-2|H_1 \cap H_2|\leq 10$

Bob Jenkins beschreibt einen solchen Code auf seiner Site , und daraus können wir das Array extrahieren

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

Da die ersten 27 Vektoren nur die 27 Zahlen des Hamming-Gewichts 1 sind, genügt es, um zu überprüfen, ob diese Konstruktion korrekt ist, alle möglich nicht trivial zu betrachten Kombinationen der letzten 25 Zahlen, wobei überprüft wird, ob ihre XORs immer mindestens 10 Hamming-Gewicht haben. Beispielsweise hat die allererste Zahl 0x07fe0000 genau 10 Hamming-Gewicht.$2^{52-27}-1 = 2^{25}-1$

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

Wie funktioniert die Darstellung? Es gibt verschiedene Optionen mit unterschiedlichen Kompromissen. Ich liste zwei unten auf.

Hartcodiertes Wörterbuch

In diesem Fall ist die Anzahl der möglichen 5-Karten-Hände so klein, dass Sie nur ein fest codiertes Wörterbuch haben könnten, in dem alle 2598960 Hände aufgelistet sind, und Sie repräsentieren eine Hand durch ihren Index im Wörterbuch (binär dargestellt).

Mit anderen Worten, das Wörterbuch kann eine sortierte Liste von Händen sein. Jede Hand ist das 5-Tupel der Karten in der Hand in sortierter Reihenfolge. Sie können mithilfe der binären Suche eine Hand im Wörterbuch nachschlagen und den entsprechenden Index finden. und mit einem Index können Sie die entsprechende Hand finden. Sie können das Wörterbuch auch als Hashmap speichern, die von der Hand auf den Index abgebildet wird. Der Index ist eine Ganzzahl zwischen 0 und 2598959, sodass er mit 23 Bit dargestellt werden kann.

Dieser Ansatz funktioniert und ist sehr einfach zu programmieren, ist jedoch platzsparend (Größe der ausführbaren Programmdatei).

Ranking / Unranking

Wenn Sie sich interessieren, gibt es alternativ bessere Methoden. Siehe z. B. eine der folgenden Referenzen:

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

• Ostseite, Westseite . Vorlesungsskript, Herbert S. Wilf, 14. August 1999. Abschnitte 3.7-3.8.

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

• /programming//q/3143142/781723

Das allgemeine Thema ist als "Rangfolge (und Nichtrangierung) von Kombinationen" bekannt. Diese sind etwas komplexer zu implementieren und zu verstehen, vermeiden jedoch die Notwendigkeit, ein fest codiertes Wörterbuch in das Programm aufzunehmen.

Sie können die fünf Elemente sortieren und gleichzeitig ohne Vergleiche auf einigen Prozessoren nach Duplikaten suchen: Angenommen, ein Prozessor verfügt über einen schnellen Befehl, der die Position des höchsten gesetzten Bits bestimmt, und einen schnellen Befehl, der eine Zahl berechnet, bei der nur das n-te Bit gesetzt ist .

Sei Bit (n) die Zahl, bei der genau das n-te Bit gesetzt ist. Sei das höchste Bit (x) die Nummer des höchsten Bits, das in der Zahl x gesetzt ist, mit einem nicht spezifizierten Wert, wenn x = 0. Sei x ^ y das Exklusiv-oder von x und y.

Gegeben sind fünf Zahlen a, b, c, d und e von jeweils 0 bis 51, die die fünf Karten in der Hand darstellen.

Sei x = Bit (a) ^ Bit (b) ^ Bit (c) ^ Bit (d) ^ Bit (e).

Sei A = höchstes_Bit (x), ändere x in x ^ Bit (A).

Sei B = höchstes Bit (x), ändere x in x ^ Bit (B).

Sei C = höchstes_Bit (x), ändere x in x ^ Bit (C).

Sei D = höchstes Bit (x), ändere x in x ^ Bit (D).

Sei E = höchstes Bit (x).

Wenn x = 0, gab es Duplikate in den Zahlen a, b, c, d und e. Verwenden Sie andernfalls A * Bit (24) + B * Bit (18) + C * Bit (12) + D * Bit (6) + E als Codierung der Hand, wobei A, B, C, D und E sind wie oben definiert. Dadurch wird eine Hand als 30-Bit-Zeichenfolge codiert, während die Sortierung auf sehr effiziente Weise durchgeführt wird.