The secretary problem

secretary_problem.py

#!/usr/bin/env python
import random
from math import e

n_runs = 1000
n_scores = 1000
score_max = 1000000


def main():
    # A success is when the best score is among the first n/e candidates
    successes = 0
    for x in range(n_runs):
        (real_best, maybe_best) = generate_best_scores(n_scores)
        if real_best == maybe_best:
            successes += 1
    print "Success rate over %d n_runs with %d candidates is %s" % (n_runs, n_scores, round(float(successes) / n_runs * 100, 2))


def get_scores(n):
    # Just a random list of integers, as our "scores" (random.sample is awfully slow)
    return [random.randint(1, score_max) for x in range(n)]


def generate_best_scores(n):
    """
    Out of a set of random numbers, returns the real max score
    and the max score among the first n/e items
    """
    scores = get_scores(n)
    stop_at = int(len(scores) / e)

    return max(scores), max(scores[0:stop_at])


if __name__ == "__main__":
    main()