Sign in to follow this  
ascii

combo numbering

Recommended Posts

ascii    133
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 this post


Link to post
Share on other sites
dalep    331
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 this post


Link to post
Share on other sites
stylin    758
Quick and easy, like baking a cake:

1. First, sort your deck by suit and rank. Possibly As through Kd
2. 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 this post


Link to post
Share on other sites
ascii    133
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 stylin
Quick and easy, like baking a cake:

1. First, sort your deck by suit and rank. Possibly As through Kd
2. 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 this post


Link to post
Share on other sites
stylin    758
Quote:
Original post by ascii
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.

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 this post


Link to post
Share on other sites
Guest Anonymous Poster   
Guest Anonymous Poster
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 this post


Link to post
Share on other sites
stylin    758
Quote:
Original post by Anonymous Poster
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...

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 this post


Link to post
Share on other sites
LilBudyWizer    491
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 this post


Link to post
Share on other sites
LilBudyWizer    491
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 this post


Link to post
Share on other sites
ascii    133
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 this post


Link to post
Share on other sites
LilBudyWizer    491
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 this post


Link to post
Share on other sites
samv    312
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 this post


Link to post
Share on other sites
Guest Anonymous Poster   
Guest Anonymous Poster
set of countable objects binary correspondence with natural numbers (a preorder)

Share this post


Link to post
Share on other sites
ascii    133
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 this post


Link to post
Share on other sites
samv    312
I'm not sure I understand what you're asking. Are you talking about binom() or about rank()?

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 this post


Link to post
Share on other sites
LilBudyWizer    491
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 this post


Link to post
Share on other sites
samv    312
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;
}

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this