Verifying Combination of Cards for Two Players

[KFC]

Hi there,
I am writing a program to verify the total combination of dealing 10 cards to two players out of 52 cards. The math is simple. Firstly, the total way to draw 10 cards from 52 is C(52, 10) = 15820024220. From the drawn 10 cards, we pick any 5 for player A and the rest of player B, total combination is C(10,5) = 252. Hence, there are total 15820024220*252 = 3986646103440 ways to deal 10 cards from 52 to two player. We can also consider this problem by first draw 5 cards out of 52 for player A, and then draw another 5 cards from the rest 47 cards for player B, which also give C(52,5)*C(47,5) 3986646103440

I am trying to loop all possible cases to repeat this number. My program is something like this

for (H1: each hand in total combination) // total 2598960 hands
begin
for (H2: each hand in total combination) // total 2598960 hands
begin
if (H1 not same as H2) increase count
end
end

this program gives the count 6754590482640 instead of 3986646103440. So anything wrong in my program or in my math? Which one is correct?

 

[CompuChip]

I think that the check has to be:
if (H1 and H2 do not have any card in common) increase count.

If H1 and H2 are exactly the same except for one card, you are now counting this as a valid possibility while it clearly is not.

 

[KFC]

I think that the check has to be:
if (H1 and H2 do not have any card in common) increase count.

If H1 and H2 are exactly the same except for one card, you are now counting this as a valid possibility while it clearly is not.

Thank you for your reply. In my code, H1 and H2 are sorted such that the cards rank least go first, so the check is actually be

if NOT ((H1[0]=H2[0]) and (H1[1]=H2[1]) and (H1[2]=H2[2]) and (H1[3]=H2[3]) and (H1[4]=H2[4]) ) increase count

but it still gives 6754590482640

 

[dacruick]

I don't think I quite understand how you want to loop through to get that number

 

[KFC]

I don't think I quite understand how you want to loop through to get that number

To verify the number is just a sanity check, actually, I need to make sure these two loops do give me all valid and possible combination for 10 cards out of 52 dealt to two players. If I can't get those two numbers match, I think there must be some states missing.

 

[dacruick]

To verify the number is just a sanity check, actually, I need to make sure these two loops do give me all valid and possible combination for 10 cards out of 52 dealt to two players. If I can't get those two numbers match, I think there must be some states missing.

What I meant was that I don't understand the mathematical operations that you are using to count up to 6 trillion?

 

[CompuChip]

Thank you for your reply. In my code, H1 and H2 are sorted such that the cards rank least go first, so the check is actually be

if NOT ((H1[0]=H2[0]) and (H1[1]=H2[1]) and (H1[2]=H2[2]) and (H1[3]=H2[3]) and (H1[4]=H2[4]) ) increase count

but it still gives 6754590482640

Can you please try:

if (NOT (H1[0]=H2[0]) and (NOT H1[1]=H2[1]) and (NOT H1[2]=H2[2]) and (NOT H1[3]=H2[3]) and (NOT H1[4]=H2[4]) ) increase count

 

[Anger]

6754590482640 is actually 2598960 * (2598960 -1), which tells us that your condition only counts the case that they have the exact same hand.


the statement below is true only when all cards are the same:

(H1[0]=H2[0]) and (H1[1]=H2[1]) and (H1[2]=H2[2]) and (H1[3]=H2[3]) and (H1[4]=H2[4])

while you want the case where at least one card is the same:

(H1[0]=H2[0]) or (H1[1]=H2[1]) or (H1[2]=H2[2]) or (H1[3]=H2[3]) or (H1[4]=H2[4])


Now, because you actually want to "enter" the if-statement when that is NOT the cause,

You get NOT( (H1[0]=H2[0]) or (H1[1]=H2[1]) or (H1[2]=H2[2]) or (H1[3]=H2[3]) or (H1[4]=H2[4]) ).

By using DeMorgan's Law you can easily see that you get the expression CompuChip suggests in the above post.

 

[KFC]

Can you please try:

if (NOT (H1[0]=H2[0]) and (NOT H1[1]=H2[1]) and (NOT H1[2]=H2[2]) and (NOT H1[3]=H2[3]) and (NOT H1[4]=H2[4]) ) increase count

Thanks. It seems not works. To simply the problem, I try to deal 8 cards out of 20 cards to two players each have 4-card hand and I get from math that the combination is

C(20, 8)*C(8,4) = 46558512

but from the program (impose the check from CompuChip already), I get 135926152


BTW just find one problem in my math analysis, there I said to deal 10 cards from 52 to 2 player with each get 5-card hand, the total combination is

C(52, 10)*C(10,5) = 3986646103440

or we can consider the situtation as follow: to deal 5 card from 52 to the first player and then deal another 5 card from the left 47 cards to the second one, i.e.

C(52,5)*C(47,5) = 3986646103440

But I just find that this is not general. If I change the question to how many ways could it be to deal 8 card to two player with each get 4-card hand. Then

C(52, 8)*C(8,4) = 42142136400

but

C(52, 4)*C(48, 4) = 52677670500


So which way is the correct way to tell the total combination? Is there any general form?

 

[jambaugh]

Two suggestions.
First try iterating through every 10 card hand, then in a smaller loop iterate through picking 5 of these to be player 1's.

Second try iterating through the cases where you toggle a flag for each of the 52 cards indicating that it is 1 (player 1's) 2 (player 2's) or 0 not drawn.

[EDIT] One issue with over counting may be that you are sorting the cards so many counted outcomes (different order of cards in the hands) yield the same hands.

 

[KFC]

Two suggestions.
First try iterating through every 10 card hand, then in a smaller loop iterate through picking 5 of these to be player 1's.

Second try iterating through the cases where you toggle a flag for each of the 52 cards indicating that it is 1 (player 1's) 2 (player 2's) or 0 not drawn.

[EDIT] One issue with over counting may be that you are sorting the cards so many counted outcomes (different order of cards in the hands) yield the same hands.

Thank you jambaugh. For the first suggestion, it works. But I am more interesting the second one. The reason is I was provided with all possible 5-card combinations of 52 cards. Hence, I need to nest my loop to iterate through the 5-card pool and skip the duplicated hands. But seems it is not enough to only considering if two hands are identical card by card, so my check will still give overcouting, right? Could you please show me more information because I don't really your second suggestion. Thanks.

 

[HYSL]

In the program/algorithm, the check condition might be a problem. If H1 is (say) 1,2,3,4,5 and H2 is 2,3,4,5,6, then H1[0] != H2[0], H1[1] != H2[1], etc., but in this case you have overlaps that are not valid.

In the 20 card example, the correct number should be

C(20,4)*C(16,4) = C(20,8)*C(8,4) = 20!/(4! 4! 12!)

Think of it this way: you are dividing the cards into three groups, player A, B and the left-overs. Play A has 4 cards, B has 4 cards, and there are 12 left-overs. The 20! gives all combinations, but you divide by 4! (player A doesn't care about the order), and 4! (player B doesn't care about the order), and 12! (the order in the left-overs don't matter). In general, if there are N cards, and you divide them into groups with n1, n2, n3, ... cards, then

N = n1 + n2 + n3 + ...

and the total number of combinations (where order within each group does not matter) is

N!/(n1! n2! n3! ...) = C(N, n1)*C(N-n1,n2)*C(N-n1-n2,n3)*...

 

[CompuChip]

OK, then the only thing I can think of is

bool handsHaveOverlap = false;
for (int i = 0; i < 5; ++i)
{
  for (int j = 0; j < 5; ++j)
  {
    if (hand1[i] == hand2[j])
    {
      handsHaveOverlap = true;
    }
  }
}

if (!handsHaveOverlap)
{
  ++numberOfHands;
}

 

[KFC]

In the program/algorithm, the check condition might be a problem. If H1 is (say) 1,2,3,4,5 and H2 is 2,3,4,5,6, then H1[0] != H2[0], H1[1] != H2[1], etc., but in this case you have overlaps that are not valid.

In the 20 card example, the correct number should be

C(20,4)*C(16,4) = C(20,8)*C(8,4) = 20!/(4! 4! 12!)

Think of it this way: you are dividing the cards into three groups, player A, B and the left-overs. Play A has 4 cards, B has 4 cards, and there are 12 left-overs. The 20! gives all combinations, but you divide by 4! (player A doesn't care about the order), and 4! (player B doesn't care about the order), and 12! (the order in the left-overs don't matter). In general, if there are N cards, and you divide them into groups with n1, n2, n3, ... cards, then

N = n1 + n2 + n3 + ...

and the total number of combinations (where order within each group does not matter) is

N!/(n1! n2! n3! ...) = C(N, n1)*C(N-n1,n2)*C(N-n1-n2,n3)*...

Thank you so much for your clarification. I found that if I modify check condition as follow and it works

if (no card in player 1's hand found in player 2's hand) then increse count

and I think it gives the correct number now.

On working this problem, I come up an idea to deal with the card dealing with only the ranking of a hand matter. We number the 52 cards as
0, 1, 2, 3, ... 49, 50, 51. All possible rankings for 5 cards are royal flush, straight flush, ..., high card (total 10 ranks).
For a 52-card deck, it is possible to deal 7462 groups of hands with all hands in one group ranking the same.
For example, for royal flush, all possible hands are

"8-9-10-11-12" (while 12 stands for high ACE spade)
"21-22-23-24-25" (while 25 stands for high ACE heart)
"34-35-36-37-38" (while 38 stands for high ACE club)
"47-48-49-50-51" (while 51 stands for high ACE diamond)

all these 4 hands belong to one group (rank the top).

I have verified by programming that to pick any 5 cards from 52, the total number of group with distinct ranking is 7462. I want to know how many way to deal 10 cards (5 to player 1 and 5 to player 2) follwing the group ranking.

For example, convert two royal-flush hands 8-9-10-11-12 and 21-22-23-24-25 into card ranking, we have 8-9-10-11-12 and 8-9-10-11-12, both rank the same (royal flush). But for 0S-1S-2S-3S-5H and 0H-1H-2H-3H-5H, they belongs to different group even the card face values are the same.

Here is how my programming to loop all the cases

for (each groupA in group1 to group7462)
begin
for (each groupB in group1 to group7462)
begin
if (no card in groupA found in groupB) increase the count
end
end

then the count gives 10837988. But how do I prove in math that this is a correct number?

 

[jambaugh]

Thank you jambaugh. For the first suggestion, it works. But I am more interesting the second one. The reason is I was provided with all possible 5-card combinations of 52 cards. Hence, I need to nest my loop to iterate through the 5-card pool and skip the duplicated hands. But seems it is not enough to only considering if two hands are identical card by card, so my check will still give overcouting, right? Could you please show me more information because I don't really your second suggestion. Thanks.

My thought of using flags is not efficient, one may just as easily use indices and use less memory:

Here's how I'd do it: Representing the cards by numbers from 1 to 52...

Player 1 loops:
For C1 from 1 to 48: For C2 = C1+1 to 49: For C3= C2+1 to 50: For C4 = C3+1 to 51: For C5 = C4+1 to 52:

Player 2 loops identical with say D1 ... D5: except as each loop increments check if its value is one of C1 through C5, if so then do nothing otherwise carry out the next level of looping.

Inside inner most loop after checking for "collision" increment your counter and if you want a copy print the hands to a file.
[EDIT: Here's a working example in Python. It takes about 1 second to iterate through the 2nd players hands so should take about 30 days to run. (Python is an interpreted lang. so is a bit slow).

Count = 0

for C1 in xrange(0,52):
    for C2 in xrange(C1+1,49):
        for C3 in xrange(C2+1,50):
            for C4 in xrange(C3+1,51):
                for C5 in xrange(C4+1,52):
                    H1 = [C1,C2,C3,C4]
                    for D1 in xrange(0,52):
                        if not D1 in H1:
                            for D2 in xrange(C1+1,49):
                                if not D2 in H1:
                                    for D3 in xrange(C2+1,50):
                                        if not D3 in H1:
                                            for D4 in xrange(C3+1,51):
                                                if not D4 in H1:
                                                    for D5 in xrange(C4+1,52):
                                                        if not D5 in H1:
                                                            Count += 1
print Count

 

[KFC]

Thanks, jambaugh. But the algorithm you post is too slow. I have read so many reference and article about combination. Finally, I select c++ STL, it only takes me 6 hours to iterate all possible hands. However, it is still slow. My through is since the card face value and suit doesn't matter, we only need to know the card ranking and the hand ranking. Why don't we divide all possible into groups (or a map), assign each group an unique index (which consists of a ranking and 5 card values). Then there are total 7462 groups.
Here is how my programming to loop all the cases

for (each groupA in group1 to group7462)
begin
for (each groupB in group1 to group7462)
begin
if (no card in groupA found in groupB) increase the count
end
end

It runs really fast, within 10 minutes. Just don't know if really give me the right number of all combination or not.

 

[jambaugh]

Thanks, jambaugh. But the algorithm you post is too slow.

Oh, well if it's speed you want just do the calculation...

52!/(42! 5! 5!)

My through is since the card face value and suit doesn't matter, we only need to know the card ranking and the hand ranking. Why don't we divide all possible into groups (or a map), assign each group an unique index (which consists of a ranking and 5 card values). Then there are total 7462 groups.

The problem with grouping is that though face and suit don't matter, the distinguishability of the cards does matter to avoid miscounting overlapping hands.

For example you should count e.g. H1=[3H,3D,4D,5D], H2 = [3S,4C,7D,10S] but not count:
H1=[3H,3D,4D,5D], H2 = [3D,4C,7D,10S] (since 3 of diamonds is in both hands).

I don't see how you're going to be able to avoid miscounting if you're iterating over groups.

-------------
Let me think about some ways to speed it up. I'll post if I think of anything good.