3 ms·
Nerd sniped. I couldn't help it. What do you think> :-) from math import e, floor from random import randint def secretary_search(candidates):
by carapace 9y ago
Nerd sniped. I couldn't help it. What do you think> :-)
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
- Bromskloss 9y agoMy version! [0] - 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/9d735c5c77bd2e0939c69f5dd4140cd4 https://gist.github.com/anonymous/9d735c5c77bd2e0939c69f5dd4... [1] https://en.wikipedia.org/wiki/Secretary_problem#Deriving_the_optimal_policy https://en.wikipedia.org/wiki/Secretary_problem#Deriving_the...