percent_37_rule.py

import math
import random
import matplotlib.pyplot as plt

def generate_candidates(M):
    r = list(range(M))
    random.shuffle(r)
    return r

def percent_n_in_m_rule(N, M):
    # generate candidates
    candidates = generate_candidates(M)
    # observation
    observation_best = candidates[0]
    observation_number = N
    for i in range(observation_number):
        candidate = candidates[i]
        if candidate > observation_best:
            observation_best = candidate
    # selection
    best = None
    for i in range(M - observation_number):
        candidate = candidates[i + observation_number]
        if candidate > observation_best:
            best = candidate
    if best == None:
        return candidates[-1]
    return best

def test_percent_37_rule():
    result = {}
    experiments_number = 1000
    M = 100
    N = int(M / math.e)
    for _ in range(experiments_number):
        best = percent_n_in_m_rule(N=N, M=M)
        if best not in result.keys():
            result[best] = 1
        result[best] += 1
    plt.bar(x=result.keys(), height=result.values())
    plt.show()

def test_percent_n_in_m_rule():
    experiments_number = 5000
    M = 100
    result = {}
    for N in range(M):
        best_result = [0 for i in range(M)]
        for _ in range(experiments_number):
            best_result[percent_n_in_m_rule(N=N, M=M)] += 1
        best_rate = best_result[-1] / experiments_number
        print(f"{N} {M} {best_rate}")
        result[N] = best_rate
    plt.plot(result.keys(), result.values())
    plt.show()

test_percent_37_rule()
test_percent_n_in_m_rule()