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;
}
combo numbering
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.
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;}
Author
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.
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.
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):
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;}
Author
I ran it, and it works. It does seem to be a bit faster, and it looks like it is O(k).
Good stuff.
Good stuff.
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.
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;}This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
