combo numbering

Recommended Posts

If you have 52 cards and you choose 7, there are 133,784,560 possibilities. So, let's say you have 7 playing cards. Is there an easy way to convert these cards into a number between 0 and 133,784,559?

Share on other sites
Just any ol' number or does each "hand" need to result in a unique signiture?

I imagine its the latter you want. You'll need seven bytes, I guess - one byte for each card. Then you'll need to assign a value from 1 to 52 to each card. You can stuff that into a 64-bit integer with room to spare.

This gives you perfect uniqueness - so the same cards in a different order result in a different signiture.

You only need 6 bits to express 52 values but I think it would be a nuissance to get into all the shifting that you'd need to use 6 bit values. And that still adds up to 42 bits so you'd still be looking at a long.

Share on other sites
Quick and easy, like baking a cake:
1. First, sort your deck by suit and rank. Possibly As through Kd2. Give each card in the deck a value from 1 to 52.3. Draw a card, read its value. That's your conversion.4. For every other card drawn ...   a. renumber the list (1..51 for a second draw)   b. draw a card.   c. multiply its value by your previous value = your conversion   e. repeat

As you can see a hand of As, 2s, 3s, 4s, 5s, 6s and 7s will equal 1. Kd, Qd, Jd, Td, 9d, 8d, 7d will be equal to some big number larger than the value you specified because it doesn't make a distinction for reordered combinations; those are included as well.

Share on other sites
The numbers must be between 0 and 133,784,559.

Here's an example using your mechanism:

52*51*50*49*48*47*46 = 674,274,182,400

As you can see, it's well out of range.

Quote:
 Original post by stylinQuick and easy, like baking a cake:1. First, sort your deck by suit and rank. Possibly As through Kd2. Give each card in the deck a value from 1 to 52.3. Draw a card, read its value. That's your conversion.4. For every other card drawn ... a. renumber the list (1..51 for a second draw) b. draw a card. c. multiply its value by your previous value = your conversion e. repeatAs you can see a hand of As, 2s, 3s, 4s, 5s, 6s and 7s will equal 1. Kd, Qd, Jd, Td, 9d, 8d, 7d will be equal to some big number larger than the value you specified because it doesn't make a distinction for reordered combinations; those are included as well.

Share on other sites
Quote:
 Original post by asciiThe numbers must be between 0 and 133,784,559.Here's an example using your mechanism:52*51*50*49*48*47*46 = 674,274,182,400As you can see, it's well out of range.

As you can see, I told you it would be:
Quote:
 Original post by stylin Kd, Qd, Jd, Td, 9d, 8d, 7d will be equal to some big number larger than the value you specified because it doesn't make a distinction for reordered combinations; those are included as well.

Post your method (it's been a few years since math class) for finding that quantity and I'll adapt my solution accordingly. You can't expect a one-to-one correspondence from just any arbitrary number, you know.

Share on other sites
well stylin's method would fit into the range you want if you just sort the hand first.

Share on other sites
We can expect such a 1 to 1 correspondence to exist. Such a correspondence must exist. The trouble is finding a correspondence that would let us easily convert from the cards to the number...well, an easy way would be to simply enumerate all the possibilities while numbering them, and then when we encounter the given cards, we have the number. Of course this is easy but not very efficient...

Maybe you could make a decision tree. Each node asks if a certain card is present or not, and you can precalculate the number of possibilities where the answer would be yes and the number of possibilities where it would be no for each node. This information allows ranges of numbers to be allocated appropriately, and at the leaves only one number would be left. But this tree would be very large...but it would have a very regular structure, so there would probably be no need to actually store the tree, the nodes would just be calculated as it was traversed.

Share on other sites
Quote:
 Original post by Anonymous PosterWe can expect such a 1 to 1 correspondence to exist. Such a correspondence must exist. The trouble is finding a correspondence that would let us easily convert from the cards to the number...well, an easy way would be to simply enumerate all the possibilities while numbering them, and then when we encounter the given cards, we have the number. Of course this is easy but not very efficient...

The difficulty - at least my difficulty - is finding a correspondence to a number that is totally out of context. My method will map all the combinations of a 7 card draw - indeed, the formula OP posted does just that; but this is not what OP wants, obviously. It's imperative to know what combinations he's excluding from the list. How can you give any sort of mapping scheme unless you know that?

Share on other sites
It's certainly possible. You can list all possible hands and then enumerate the hands by their position in the list. You can do that algorithmically by using the process you used to generate the list rather than storing the list. It's basically a sequential search of the list. So, yes, it is certainly possible because there is a way to do it.

Over 60 million iterations of a loop on average for both encoding and decoding just isn't a practical approach. Can you reduce that? Most certainly. Assuming you are generating hands with loops nested seven levels deep there really is no reason for the innermost loop. You have to find a base number for the first six cards, but you can convert the seventh directly into an offset off that base. Can you reduce it further?

That depends upon whether you can find a way to uniquely enumerate all two card hands. So that's really the essence of the problem. That gets it down to a size you can quickly and easily test theories as to how you might do that encoding.

Share on other sites
So anyway, you want to enumerate two card hands. Say you decide {0,1}=0, {0,2}=1, {0,51}=51, {1,2}=52, and so forth. There are 51 hands where C[0]=0, 50 where C[0]=1, 49 where C[0]=2, etc. So there are sum(51-n,n,0,k-1) hands that started with a lower card than k. That can be restated as (k*(2*l-k+1))/2 where l is 51. So (C[0]*(2*51-C[0]+1))/2 + (C[1]-C[0]-1) will uniquely enumerate the two card hands using the range 0 to 1325.

Now it'll take a little work to do that for a seven card hand, but the same process will work. You find the number of hands starting with a card less then the first card. You then find the number of hands starting with the first card where the second card is less than the second card. You continue that process for every card, add up the numbers and that is the enumeration for the hand.

The summation formula is pretty simple. It's just picks. So if the first card is k then sum(pick(6,51-n),n,0,k-1). Simplifying the formula most likely isn't worth the effort. The worst case, which can't actually happen, is that you calculate the pick 50*7 times. It's actually far less. If you don't actually simplify the formula then reversing the process is much easier.

Share on other sites
This seems to work:

long choose(int n, int k)
{
long long numerator = 1;
for (int ctr = 0; ctr < k; ctr++) numerator*=(n - ctr);
for (int ctr = 1; ctr <= k; ctr++) numerator/=ctr;
return numerator;
}

long rank(Card cards[7])
{
long therank=0;
for (int k = 1; k <= 7; k++)
{
int x1 = cards[k-1].getcardnum();
x1-= 7-k;
therank += choose(52, k) - choose(52 - x1, k);
}
return therank;
}

Share on other sites
You can test it using bit flags or bytes to verify each number was generated once and only once. Make sure you sort the hands so that each distinct hand is uniquely specified.

Share on other sites
Another solution without explanations [wink]
#include <iostream>#include <algorithm>class Card{public:	Card(int num) : num(num) {}	int getcardnum() { return num; }	int num;};bool is_above(const Card &a,const Card &b) { return a.num>b.num; }int binom(int n,int m){	// = n! / (m! * (n-m)!)	if(m + m>n)m=n-m;	if(m<0)return 0;	int result=1;	for(int i=1;i<=m;i++) result=(result*(n-i+1))/i;	return result;}int rank(int n,int m,Card cards[]){	int result=0;	std::sort(cards,cards+m,is_above);	for(int a=1;a<=m;a++)		for(int i=1;i<=cards[a-1].getcardnum()-m+a;i++)			result+=binom(n-cards[a-1].getcardnum()-2+i,a-1);	return result;}int main(){	const int n=52,m=7;	Card cards_0[m]={ 6,5,4,3,2,1,0 };//0	Card cards_2[m]={ 8,5,4,3,2,1,0 };//2	Card cards_big[m]={ 51,50,49,48,47,46,45 };//133784559	std::cout		<<((rank(n,m,cards_0)==0)?"ok\n":"oops\n")		<<((rank(n,m,cards_2)==2)?"ok\n":"oops\n")		<<((rank(n,m,cards_big)==133784559)?"ok\n":"oops\n");	return 0;}

Share on other sites
set of countable objects binary correspondence with natural numbers (a preorder)

Share on other sites
Ok, so for n choose k, what is the best running time of a ranking algorithm?

Is it O(k) or O(nk)?

sam's algorithm seems to work, but it's O(nk). I think O(k) might be possible.

Share on other sites

I found the algorithm to calculate the binomial coefficients on Wikipedia (Sorry for the german link. The english equivalent seems to be missing this tidbit).

Also, Maple told me this should be equivalent, and it looks faster (altough I didn't check):
int rank(int n,int m,Card cards[]){	int result=0;	std::sort(cards,cards+m,is_above);	for(int a=1;a<=m;a++)	{		int n_ = n-cards[a-1].getcardnum()-2;		int k_ = cards[a-1].getcardnum()-m+a;		int m_ = a-1;		result+=((n_+k_+1-m_)*binom(n_+k_+1,m_)-(n_+1-m_)*binom(n_+1,m_))/(m_+1);	}	return result;}

Share on other sites
I ran it, and it works. It does seem to be a bit faster, and it looks like it is O(k).

Good stuff.

Share on other sites
One consideration is whether you can use a 6 column table with 46 entries to do the encoding/decoding and completely eliminate the picking except for building the table. I haven't thought about it in detail so I can't swear it is, but it seems possible.

Share on other sites
Since I was bored, here is the another minor simplification (which also makes it look a bit less messy):
int rank(int n,int m,Card cards[]){	int result=0;	std::sort(cards,cards+m,is_above);	for(int a=0;a<m;a++)	{		int p = n-m;		int q = n-a-cards[a].getcardnum()-1;		result+=(p*binom(p+a,a)-q*binom(q+a,a))/(a+1);	}	return result;}

Create an account

Register a new account

• Forum Statistics

• Total Topics
628301
• Total Posts
2981912

• 10
• 11
• 11
• 10
• 10