There's probably no lack of toy code, but since I am a skeptic / sceptic, quick nonsense code for pythonistas : https://gist.github.com/anonymous/ef975cdcb26044de9ba93e4e74...
Guess what? Skepticism allayed!
Guess what? Skepticism allayed!
from math import e, floor
from random import randint
def secretary_search(candidates):
"""Rejects first n / e candidates and then selects the first better."""
n_reject = int(floor(len(candidates) / e))
best = max(candidates[:n_reject])
for candidate in candidates[n_reject:]:
if candidate > best:
return candidate
return candidates[-1]
success = 0.0
size = 100
trials = 10000
for _ in range(trials):
candidates = [randint(1, 1000) for _ in range(size)]
success += max(candidates) == secretary_search(candidates)
print success / trials- More functional, with iterators and stuff. (It's half-baked, though, so please take it further!)
- Handles small numbers of candidates correctly.
- Agrees with the table on Wikipedia [1], and with the 1/e limit.
- Calculates hiring frequency for all candidates, not just the best one.
- Faster!
[0] https://gist.github.com/anonymous/9d735c5c77bd2e0939c69f5dd4...
[1] https://en.wikipedia.org/wiki/Secretary_problem#Deriving_the...