patternModerate
Represent a 5 card poker hand
Viewed 0 times
pokerhandcardrepresent
Problem
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
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 tri
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 quickSort = new SortedSet() { 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 tri
Solution
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:
-
https://en.wikipedia.org/wiki/Combinatorial_number_system
-
East Side, West Side. Lecture notes, Herbert S. Wilf, August 14, 1999. Sections 3.7-3.8.
-
https://computationalcombinatorics.wordpress.com/2012/09/10/ranking-and-unranking-of-combinations-and-permutations/
-
https://stackoverflow.com/q/3143142/781723
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.
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:
-
https://en.wikipedia.org/wiki/Combinatorial_number_system
-
East Side, West Side. Lecture notes, Herbert S. Wilf, August 14, 1999. Sections 3.7-3.8.
-
https://computationalcombinatorics.wordpress.com/2012/09/10/ranking-and-unranking-of-combinations-and-permutations/
-
https://stackoverflow.com/q/3143142/781723
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.
Context
StackExchange Computer Science Q#72542, answer score: 13
Revisions (0)
No revisions yet.