from random import betavariate, shuffle

def binomialvariate(n, p):
    if n == 0:
        return 0
    a, b = (1 + n)//2, 1 + n//2
    x = betavariate(a, b)
    if x < p:
        return a + binomialvariate(b - 1, (p - x)/(1 - x))
    else:
        return binomialvariate(a - 1, p/x)

def choices(population, weights, *, k=1):
    r = 1.0
    n = k
    selections = []
    for elem, p in zip(population, weights):
        v = binomialvariate(n, p / r)
        selections += [elem] * v
        n -= v
        r -= p
    shuffle(selections)
    return selections

if __name__ == '__main__':

    from collections import Counter

    print(sorted(Counter(choices('ABCD', (0.10, 0.30, 0.20, 0.40), k=100_000)).items()))