11
$\begingroup$

A deck of cards is 52. A hand is 5 cards from the 52 (cannot have a duplicate).

What is the least amount of bits to represent a 5 card hand and how?
A hand is NOT order dependent (KQ = QK). 64329 = 96432

Yes, can use 52 bits. That can represent a hand of any number of cards.

Given a hand is exactly 5 cards is there a way to represent it with less than 52 bits.

A single card can be represented with 6 bits = 64. So could just use 6 bits * 5 cards = 30 bits. But that would be order dependent. I could just sort and this should work. If that would not work please let me know.

Is there a way to get the key to 32 bits or under and not have to sort the 5 card tuple.

This is for poker simulations and sorting would be a lot of overhead compared to just generating the hand. If I have a dictionary with the relative value of each hand it is two simple lookups and a comparison to compare the value of two hands. If I have to sort the hands first that is large compared to two lookups and a comparison. In a simulation will compare millions. I will not get sorted hands from the simulation. The sort is not simple like 52 51 50 49 48 before 52 51 50 49 47. You can have straight flush quads ....

There are 2598960 possible 5 card hands. That is the number of rows. The key is the 5 cards. I would like to get a key that is 32 bits or under where the the cards do not need to be sorted first.

Cannot just order the list as many hands tie. Suit are spade, club, diamond, and heart. 7c 8c 2d 3d 4s = 7s 8s 2c 3c 4h. There is a large number of ties.

The next step is 64 bits and will take the hit of the sort rather than double the size of the key.

I tested and SortedSet<int> quickSort = new SortedSet<int>() { i, j, k, m, n }; doubles the time of the operation but I still may do it.

It gets more complex. I need to be able to represent a boat as twos over fives (22255). So sorting them breaks that. I know you are going to say but that is fast. Yes it is fast and trivial but I need as fast as possible.

C# for the accepted answer: 

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("");
}
Improve this question
$\endgroup$
11
  • 4
    $\begingroup$ Use a hand-coded sorting algorithm which works for sorting lists of length 5. This is probably faster than the library function you're currently using. $\endgroup$
    – Yuval Filmus
    Commented Apr 5, 2017 at 20:47
  • 1
    $\begingroup$ I don't understand why you say "The sort is not simple". The sort is simple -- convert each card to a number from 1 to 52, so that the hand is represented by a list (of length 5) of cards. Sort that list. That is just the problem of sorting a list of 5 integers, which can be done very fast, as Yuval mentions. I suggest that you measure before assuming that it is too slow, but my guess is that sorting such a list will be very fast and might even be faster than a random-access memory read that doesn't hit in the cache. $\endgroup$
    – D.W. ♦
    Commented Apr 5, 2017 at 21:49
  • $\begingroup$ @dw Yes the sort is simple but what I am doing (millions of times) is simple. I tested and a sort doubles the time. $\endgroup$
    – paparazzo
    Commented Apr 6, 2017 at 0:37
  • 1
    $\begingroup$ @Paparazzi No, Yuval is telling you to write your own sorting routine that is specifically tuned to sorting five numbers between 1 and 52. You tried using a library routine, which is slow because it is much more general than this and because the recursive nature of quicksort makes it very inefficient on short lists. $\endgroup$
    – David Richerby
    Commented Apr 6, 2017 at 8:48
  • $\begingroup$ In practice, most items that are not <=16 bits might as well be 32 bits. So since you need at least 23 bits, any encoding which uses <=32 bits is probably viable. The trivial 6 bits per card * 5 card encoding works well enough. There's one caveat: a 23 bit array index is much better than a 32 bits array index. $\endgroup$
    – MSalters
    Commented Apr 6, 2017 at 9:00

3 Answers 3

Reset to default
10
$\begingroup$

Let $C$ be a $[52,25,11]$ code. The parity check matrix of $C$ is a $27 \times 52$ bit matrix such that the minimal number of columns whose XOR vanishes is $11$. Denote the $52$ columns by $A_1,\ldots,A_{52}$. We can identify each $A_i$ as a binary number of length $27$ bits. The promise is that the XOR of any $1$ to $10$ of these numbers is never $0$. Using this, you can encode your hand $a,b,c,d,e$ as $A_a \oplus A_b \oplus A_c \oplus A_d \oplus A_e$, where $\oplus$ is XOR. Indeed, clearly this doesn't depend on the order, and if two hands $H_1,H_2$ collide, then XORing the two hash values gives $10-2|H_1 \cap H_2|\leq 10$ numbers whose XOR is zero.

Bob Jenkins describes such a code in his site, and from that we can extract the array

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

Since the first 27 vectors are just the 27 numbers of Hamming weight 1, in order to check that this construction is correct it suffices to consider all $2^{52-27}-1 = 2^{25}-1$ possible non-trivial combinations of the last 25 numbers, checking that their XORs always have Hamming weight at least 10. For example, the very first number 0x07fe0000 has Hamming weight exactly 10.

Improve this answer
$\endgroup$
4
  • $\begingroup$ I don't exactly follow. How many bits does this need for a hand? $\endgroup$
    – paparazzo
    Commented Apr 6, 2017 at 16:23
  • $\begingroup$ It needs 27 bits. You can use any larger number of bits. $\endgroup$
    – Yuval Filmus
    Commented Apr 6, 2017 at 16:25
  • $\begingroup$ Thanks. I tested and the numbers are unique and <= 32 bits. Can I derive the 5 cards from the number? If not fine just asking. $\endgroup$
    – paparazzo
    Commented Apr 7, 2017 at 0:04
  • $\begingroup$ Yes, it's simple linear algebra. You can use the correct matrix to get back a vector of length 52 with 5 ones. I'll let you figure that out. $\endgroup$
    – Yuval Filmus
    Commented Apr 7, 2017 at 2:50
13
$\begingroup$

If we have a set of size $n$, you can represent an element of the set using $\lceil \lg n \rceil$ bits. You say that there are 2598960 possible 5-card hands. That means that a 5-card hand can be represented using just $\lceil \lg 2598960 \rceil = 22$ bits. 22 bits is significantly shorter than 30 bits.

How does the representation work? There are various options, with different tradeoffs. I list two below.

Hard-coded dictionary

In this case, the number of possible 5-card hands is small enough that you could just have a hard-coded dictionary that lists all 2598960 hands, and you represent a hand by its index in the dictionary (represented in binary).

In other words, the dictionary can be a sorted list of hands. Each hand is the 5-tuple of the cards in the hand, in sorted order. You can look up a hand in the dictionary using binary search and find its corresponding index; and given an index, you can find the correspond hand. Or, you could store the dictionary as a hashmap that maps from the hand to its index. The index is an integer between 0 and 2598959, so it can be represented using 23 bits.

This approach will work and be very simple to program, but it is wasteful in space (size of the program executable).

Ranking/unranking

Alternatively, if you care, there are better methods. See, e.g., any of the following references:

The general topic is known as "ranking (and unranking) of combinations". These are a little more complex to implement and understand, but avoid the need to include a hard-coded dictionary in the program.

Improve this answer
$\endgroup$
5
  • $\begingroup$ I will update the question. Yes there are 2598960 hands. The dictionary will have that many rows. My problem is generation of the key. From 5 cards I need to generate a the key to perform the dictionary lookup. $\endgroup$
    – paparazzo
    Commented Apr 5, 2017 at 20:36
  • $\begingroup$ @Paparazzi, if you use the dictionary approach, the hand is the key. In other words, the key is the 5-tuple of the cards in the hand (in sorted order). The dictionary can be stored as a hashtable using that as the key. If you don't like the memory costs of a dictionary, use the alternative approach: ranking/unranking. $\endgroup$
    – D.W. ♦
    Commented Apr 5, 2017 at 20:38
  • $\begingroup$ Yes I know I can get the key of 30 bits if I sort. I am wondering if there is a way to get the key 32 bits or under without sorting the 5 card tuple. I will look into rank and ranking. $\endgroup$
    – paparazzo
    Commented Apr 5, 2017 at 20:41
  • $\begingroup$ I don't follow the ranking / unranking but thanks. I will try and figure it out. Also have the possibilities of ties. There are a lot of ties. $\endgroup$
    – paparazzo
    Commented Apr 5, 2017 at 21:32
  • 1
    $\begingroup$ Also relevant: cs.stackexchange.com/questions/67664/… $\endgroup$
    – Pseudonym ♦
    Commented Apr 6, 2017 at 2:27
3
$\begingroup$

You can sort the five items and simultaneously check for duplicates without any comparisons on some processors: Assume a processor has a fast instruction which determines the position of the highest bit set, and a fast instruction calculating a number with only the n-th bit set.

Let bit (n) be the number with exactly the n-th bit set. Let highest_bit (x) be the number of the highest bit that is set in the number x, with an unspecified value if x = 0. Let x ^ y be the exclusive-or of x and y.

Given are five numbers a, b, c, d and e, each from 0 to 51, representing the five cards in the hand.

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

Let A = highest_bit (x), change x to x ^ bit (A).

Let B = highest_bit (x), change x to x ^ bit (B).

Let C = highest_bit (x), change x to x ^ bit (C).

Let D = highest_bit (x), change x to x ^ bit (D).

Let E = highest_bit (x).

If x = 0 then there were duplicates in the numbes a, b, c, d, and e. Otherwise, use A * bit (24) + B * bit (18) + C * bit (12) + D * bit (6) + E as the encoding of the hand, where A, B, C, D and E are defined as above. This encodes a hand as a 30-bit string, while doing the sorting in a very efficient way.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Does this use 52 bits? $\endgroup$
    – paparazzo
    Commented Apr 7, 2017 at 0:19
  • $\begingroup$ @Paparazzi, no. Take another look at the last paragraph. I edited it to try to provide even greater clarity. $\endgroup$
    – D.W. ♦
    Commented Apr 7, 2017 at 0:45
  • 1
    $\begingroup$ It requires a 64-bit CPU, but the end result is only 30 bits. $\endgroup$
    – Yuval Filmus
    Commented Apr 7, 2017 at 6:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.