Secretary problem

gistfile1.py

#Original secretary problem solution based on 100 secretaries and just on the ranking of secretaries from 1-100
#want to figure out both average ranking chosen and how often the best candidate is chosen


#function which randomizes a list
def randomize_rankings(sec):
    import random
    random.shuffle(sec)
    return sec

#function which returns a secretary based on original algorithm
def chooseSecretary(sec):
    import math
    stopping_rule = int(round(len(sec)/math.e))
    max=sec[0]
    for x in range(stopping_rule - 1):
        if (sec[x] > max):
            max = sec[x]

    for x in range(stopping_rule - 1, len(sec)):
        if (sec[x] > max):
            return sec[x]

    return sec[-1]


APPLICANTS = 100
TRIALS = 10000

sec = list(range(0, APPLICANTS))

b=0
bestCount=0
total=0
winners = list()

for b in range(TRIALS):
    secSorted = randomize_rankings(sec)
    chosen = chooseSecretary(secSorted)
    if chosen == APPLICANTS - 1:
        bestCount += 1
    total += chosen
    b += 1
    winners.append(chosen)

print "Best count: %s" % bestCount
print "Picked the best: %s" % (bestCount / float(TRIALS))
print "Average: %s" % (total / TRIALS)
print "Median: %s" % sorted(winners)[len(winners)//2]
print "Bottom 10%% %s" % (sum(i < int(APPLICANTS / 10) for i in winners) / float(TRIALS))

#print "All Winners: %s" % sorted(winners)