Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Combination of cards

  1. Oct 12, 2011 #1

    KFC

    User Avatar

    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?
     
  2. jcsd
  3. Oct 12, 2011 #2

    CompuChip

    User Avatar
    Science Advisor
    Homework Helper

    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.
     
  4. Oct 12, 2011 #3

    KFC

    User Avatar

    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
     
  5. Oct 12, 2011 #4
    I don't think I quite understand how you want to loop through to get that number
     
  6. Oct 12, 2011 #5

    KFC

    User Avatar

    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.
     
  7. Oct 12, 2011 #6
    What I meant was that I don't understand the mathematical operations that you are using to count up to 6 trillion?
     
  8. Oct 12, 2011 #7

    CompuChip

    User Avatar
    Science Advisor
    Homework Helper

    Can you please try:
    Code (Text):

    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

     
     
  9. Oct 12, 2011 #8
    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.
     
  10. Oct 12, 2011 #9

    KFC

    User Avatar

    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?
     
    Last edited: Oct 12, 2011
  11. Oct 12, 2011 #10

    jambaugh

    User Avatar
    Science Advisor
    Gold Member

    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.
     
  12. Oct 12, 2011 #11

    KFC

    User Avatar

    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.
     
  13. Oct 12, 2011 #12
    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)*....
     
  14. Oct 13, 2011 #13

    CompuChip

    User Avatar
    Science Advisor
    Homework Helper

    OK, then the only thing I can think of is
    Code (Text):

    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;
    }
     
     
  15. Oct 13, 2011 #14

    KFC

    User Avatar

    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?
     
  16. Oct 13, 2011 #15

    jambaugh

    User Avatar
    Science Advisor
    Gold Member

    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).
    Code (Text):

    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
     
     
    Last edited: Oct 13, 2011
  17. Oct 13, 2011 #16

    KFC

    User Avatar

    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.
     
  18. Oct 13, 2011 #17

    jambaugh

    User Avatar
    Science Advisor
    Gold Member

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

    52!/(42! 5! 5!)

    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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Combination of cards
  1. Card Games (Replies: 4)

  2. A card game (Replies: 3)

  3. Card probability (Replies: 10)

  4. Probability cards (Replies: 3)

Loading...