'''
Note: this is taken from here:
https://www.math.ucdavis.edu/~gravner/MAT135A/resources/chpr.pdf
19. You are in possession of n pairs of socks (hence a total of 2n socks) ranging in shades of
grey, labeled from 1 (white) to n (black). Take the socks blindly from a drawer and pair them
at random. What is the probability that they are paired so that the colors of any pair differ by
at most 1?
The direct solution with an explicit formula is included in the back of that article, and in fact
is the basis for our test function below! Here, you have to solve this problem
using Monte Carlo techniques as we learned in class.
You should use 10**5 (100,000) trials.
'''
import random
def trialSucceeds(n):
socks = list(range(n))*2
random.shuffle(socks)
while (socks != [ ]):
sock1 = socks.pop()
sock2 = socks.pop()
if (abs(sock1 - sock2) > 1):
return False
return True
def pairedSocksProbability(n):
trials = 10**5
successes = 0
for trial in range(trials):
if trialSucceeds(n) == True:
successes += 1
return successes / trials
def testPairedSocksProbability():
print('Testing pairedSocksProbability()...', end='')
for n in range(20):
observed = pairedSocksProbability(n)
expected = ((2**(n+1) + (-1)**n) * 2**n * factorial(n)) / (3 * factorial(2*n))
if (abs(expected - observed) > 0.05):
raise Exception(('pairedSocksProbability(%d) failed.\n' +
' The function returned %f\n' +
' The expected value is %f\n') % (n, observed, expected))
print('Passed!')
def factorial(n):
result = 1
for i in range(2, n+1): result *= i
return result
def testPairedSocksProbability():
print('Testing pairedSocksProbability()...', end='')
def factorial(n):
result = 1
for i in range(2, n+1): result *= i
return result
for n in range(8):
observed = pairedSocksProbability(n)
expected = ((2**(n+1) + (-1)**n) * 2**n * factorial(n)) / (3 * factorial(2*n))
ratio = min(observed, expected)/max(observed, expected)
print(n, ratio, observed, expected) # for debugging
if (ratio < 0.70):
raise Exception(('pairedSocksProbability(%d) failed.\n' +
' The function returned %f\n' +
' The expected value is %f\n') % (n, observed, expected))
print('Passed!')
testPairedSocksProbability()