Card Probability Question

[Home]   [Puzzles & Projects]    [Delphi Techniques]   [Math topics]   [Library]   [Utilities]

 

Search

Search WWW

Search DelphiForFun.org

As of October, 2016, Embarcadero is offering a free release of Delphi (Delphi 10.1 Berlin Starter Edition ).     There are a few restrictions, but it is a welcome step toward making more programmers aware of the joys of Delphi.  They do say "Offer may be withdrawn at any time", so don't delay if you want to check it out.  Please use the feedback link to let me know if the link stops working.

 

Support DFF - Shop

 If you shop at Amazon anyway,  consider using this link. We receive a few cents from each purchase.   Thanks.


Support DFF - Donate

 If you benefit from the website,  in terms of knowledge, entertainment value, or something otherwise useful, consider making a donation via PayPal  to help defray the costs.  (No PayPal account necessary to donate via credit card.)  Transaction is secure.

Contact

Feedback:  Send an e-mail with your comments about this program (or anything else).

Search DelphiForFun.org only

 

 

Problem Description

Given two card rank values, the question is:

What is the probability that there are one or more occurrences of the two values being adjacent or with only one intervening card in a well shuffled standard 52 card deck?
 

Background & Techniques

Viewer Kevin asked the above question,  maybe to win a few beers from his buddies - he refers to the "guesser" as the "victim".

If I were a better mathematician, I could probably come up with an analytical answer to the question.   I'm not. and I couldn't.  Even knowing the experimental answer, I haven't succeeded in setting up the permutations that define the possible outcomes. 

 The program finds the answer experimentally.  For the specified  number of trials (100,000 by default), a "deck" is "shuffled" and then checked for one or more matches meeting the specified conditions.  The deck consists of only card rank values 1 through 13 repeated 4 times to make and array of 52 integers.  .

The matching procedure is to move through the deck from cards 1 trough 50,  checking each card against the two cards following for a match against the two test values, checked in either order.  The card in position 51 is, of course, only checked against card 52 for a match in either order. 

An additional option allows checking against the immediately following card and not the 2nd following card.

If the number of matches in a deck is greater than zero, that trial counts as a success. 

Addendum - October 21,2006:  Here is a follow-up question:  Is it possible to arrange a deck so that all 78 unique rank pairs meet the condition? (In choosing pairs, we have 13 choices for the first card and 12 choices for the second or 156 altogether. But since [a,b] and b,a] are identical for our purposes, we'll divide by 2 to get 78 choices.). 

An second program "PerfectDeck", posted today, answers the question. (Yes!)

The "Check Random decks" option generates random decks and counts the pairs that meet the condition. It was not very successful; no perfect decks found in 500,0000 decks checked.

The second search type, "hill climbing", starts with a random deck and swaps pairs, keeping those that improve the score. It finds solutions rapidly, so the trial stops after 1000 are found.  There were some interesting issues in this approach.  If the pairs are chosen for swapping systematically  there are some deck configurations that will never lead to a solution  if we require each successful swap to produce a higher score.  If we allow swaps which match or exceed the current score, solutions will be found.   It would be interesting to find out what these problem configurations look like.

Addendum November 1, 2009:  I took 3 years, but  viewer Mark Rickert came up with an ingenious solution that I really like which allows exact probabilities to be calculated.  His solution was in C, but it's clever enough that I'll even forgive him for that!   I have  translated his C code to Delphi as an exercise and the button to invoke it can be seen by pressing Ctrl C in the running program.  Here's the algorithm as I implemented it in Delphi: 

Positions of the 4 cards with Card1 value can be placed in C(52,4) ways, this is the number of combinations of 4 positions within the deck.  There are about 275,000 such possibilities, which can be quickly generated.  Four each these, the 4 suits with the Card2 value can be placed across the other 48 cards in C(48,4) ways.   Checking each of these 190,000 or so possibilities for each of the 275,000 Card1 arrangements to to how many have Card1 and Card2 values near each other would be a very long process indeed. 

But Mark's key observation was that we do not need to check them all.  Instead, for each Card1  arrangement, we can identify the set of positions which are not close enough to a  Card1 to qualify as a location for Card2 to produce a  successful outcome, call them the non-neighbors.  To qualify as a failed arrangement, all 4 Card2 values must fall on these non-neighbor positions.  This can be done in C(Non-neighborCount, 4) ways .  If we subtract this number from the total number of ways that Card2 can be placed (C(48,4) remember), we are left with the number of possible successful outcomes where one or more of the Card2 cards is within the neighborhood of a Card1 for a particular Card1 arrangement.   If we repeat the calculation and sum these results for each of the 275000 Card1 arrangements, we'll have the total number of possible successful outcomes, call it SucessCount.   Probability for a random event is defined as successful outcomes divided by total possible outcomes.  P = SuccessCount / (C(52,4)*C(48,4)). 

Version 2 posted today, does this calculation.  To make testing easier, I also expanded the choices for deck size by allowing the user to enter the number suits in the deck and the number of card values for each suit.  The "Calculate Exact Probabilities" button performs the above algorithm with appropriate extensions to handle the cases where cards must be adjacent to qualify as a success and the case where Card1 value equals Card2 value.    

Running/Exploring the Program 

bullet Download  CardProbability" source
bullet Download  "CardProbability" executable
bullet Download "PerfectDeck" Source
bullet Download "PerfectDeck" executable.

Suggestions for Further Explorations

bullet November 2009  Done!  Define the analytical solution. 
bullet In "Perfect Deck" program, study the problem configurations described above.

 

Original Date: September 23, 2006

Modified: February 18, 2016

 

  [Feedback]   [Newsletters (subscribe/view)] [About me]
Copyright 2000-2017, Gary Darby    All rights reserved.