zipf.py

def zipf(n):
    # element n is weighted by 1/n
    cumulative_weight = 0
    cumulative_weights = []
    for n in range(1, n + 1):
        cumulative_weight += 1.0 / n
        cumulative_weights.append(cumulative_weight)

    total_weight = cumulative_weights[-1]
    r = random.random() * total_weight
    for i, w in enumerate(cumulative_weights):
        if r < w:
            return i