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