How did you calculate values in "choose[53][8]"

[CuthbertJungle]

Hi, this is great software and the explanation is very good. I think I follow everything except for how the values in the table choose[53][8] were derived and what they signify, not sure how we've gone from the 52 cards options and seven actual cards to the numbers in the table.

please could you help me out on this.

thanks

[HenryRLee]

Hi, the choose[53][8] table comes from the mathematical combinations. So choose[n][k], often noted as 'n choose k' in maths, basically means: in a set of n elements, how many combinations you can choose to form a k elements subset. For example if you have three different colors: red, green and blue, and you want to choose two out of them, the number of combinations is 3 (red blue, red green, green blue). So 3 choose 2 (represented as choose[3][2] in the code) is 3. Wiki: Combination

In terms of calculation, n choose k can be calculated from this formula: n!/k!(n-k)!, where n! is the factorial of n. However, in practice, we use the Pascal's triangle to build up this table, which would be a more efficient approach. Wiki: Pascal's triangle

Hope these info can help you.

[CuthbertJungle]

thanks for the prompt reply, i think i follow. do you have the code for this? i'm looking to extend your idea for looking up 2, 3 and 4 card hands so need to build a new choose table accordingly.

[HenryRLee]

I'll write you a piece of sample to show the idea. The key part is choose[i][j] = choose[i-1][j] + choose[i-1][j-1];, which calculates the current value from previous results, a typical application of dynamic programming.

long long choose[MAXN][MAXK];

for (int i = 0; i < MAXN; i++)
    choose[i][0] = 1;

for (int i = 1; i < MAXN; i++)
    for (int j = 1; j < MAXK; j++)
        choose[i][j] = choose[i-1][j] + choose[i-1][j-1];

Also note that, the table value is invariant. So, unless you want to extend the algorithm for 8-card poker hand or more, directly using my table would be sufficient. For example 7 choose 5 is always 21, the maximum number of n or k makes no difference here.

[CuthbertJungle]

using your provided code plugging in MAXN=53 and MAXK=8 to get the same size array as at 'choose[53][8]' in dptables.c i get different numbers. eg for row 53 in dptables.c we have values 1, 52, 1326, 22100, 270725, 2598960, 20358520, 133784560 whereas running the above code i get 140737508701408 and 6473924597557413 for the final 2 entries which are much bigger than expected.

[HenryRLee]

Sorry, I made a mistake. Change the second loop from 'j < MAXK && j <= i' to 'j < MAXK' would fix it. I'll fix the above comment as well.

[CuthbertJungle]

this is perfect ! thanks for all your help 👍