Secretary (Bromskloss)

secretary_bromskloss.py

#!/usr/bin/env python3                                                          
# coding: utf-8                                                                 

from math import e
from random import shuffle
from itertools import islice


def secretary_search(candidates):
    """Rejects first n / e candidates and then selects the first                
    better (or the last one, if there is no one better)."""
    n_reject = int(len(candidates) / e)
    last = candidates[-1]
    candidates = iter(candidates)
    best = max(islice(candidates, n_reject), default=-1)
    return next(filter(lambda c: c > best, candidates), last)


n_candidates = 100
assert n_candidates >= 1, "At least one candidate, please."

n_trials = 10000
candidates = list(range(n_candidates))
hires = [0]*n_candidates
for _ in range(n_trials):
    shuffle(candidates)
    hires[secretary_search(candidates)] += 1

hires = [h/n_trials for h in hires]
# print(hires)  # Probability distribution over candidates.                     
print(hires[-1])