1. import numpy as np
2. from tqdm import tqdm
3.  
4. def gen_array(n_candidates=10):
5.     """
6.     Randomly generate `n_candidates` candidate rank from 1->n_candidates
7.         Assumption: P(rank of ith candidate = k) is random uniform (1 <= i, k <= n_candidates)
8.         (meaning each position has equally chance to be the best, second best, worst, etc.)
9.        
10.     Example:
11.     >> gen_array(10)
12.     6,  5,  1,  4,  3,  7,  8,  9,  2, 10
13.     """
14.     assert n_candidates > 1
15.    
16.     return np.random.choice(range(1, n_candidates+1),
17.                             size=n_candidates,
18.                             replace=False)
19.  
20. def simulate_stop_after_r(r, n_candidates, tries=10_000):
21.     """
22.     Estimate the winning chance of "stopping after r" strategy
23.     (Winning means the best candidate overall has been picked)
24.    
25.     The stopping after r strategy:
26.         - Ignore the first r candidates
27.         - Only consider candidates from r+1 to n_candidates:
28.             - if candidate is the best so far, pick
29.             - if candidate is not the best so far, move on
30.                 until a best so far is found or ran out of candidates
31.             - pray
32.     """
33.     assert r <= n_candidates
34.    
35.     win_count = 0
36.    
37.     for _ in range(tries):
38.         arr = gen_array(n_candidates)
39.        
40.         # ignore the first r-1 candidates, but keeping tab of the best ignored
41.         best_ignored = max(arr[:r+1])
42.        
43.         found = False
44.        
45.         # consider each candidate from r+1 onwards
46.         for current in range(r+1, n_candidates):
47.        
48.            
49.             if arr[current] > best_ignored:
50.                 # pick if current is better than best ignored
51.                 pick = arr[current]
52.                 found = True
53.                 break
54.            
55.            
56.         if found:
57.             # is pick the best?
58.             if pick == n_candidates:
59.                 win_count += 1
60.              
61.    
62.     return round(win_count / tries, 4)
63.        
64.    
65. n_candidates = 10
66. p_win = dict()
67.  
68. for r in tqdm(range(n_candidates)):
69.     p_win[r] = simulate_stop_after_r(r, n_candidates)
70.  
71. print(p_win)