One-pass weighted random sample (without replacement). Based on *Weighted Random Sampling* (2005; Efraimidis, Spirakis) [https://utopia.duth.gr/~pefraimi/research/data/2007EncOfAlg.pdf]. Longer treatment here: https://krlmlr.github.io/wrswoR/articles/internal/wrswoR.html

one_pass_wrs.py

import math
import random


class Item(object):
    def __init__(self, label, weight):
        self.label = label
        self.weight = weight
        self.nonce = 0.0

    def __repr__(self):
        return f"{self.label}/w={self.weight}/nn={self.nonce}"

    def __str__(self):
        return self.label


items = [
    Item("ff", 100),
    Item("ll", 5),
    Item("ak", 99),
    Item("cf", 100),
]

for i in items:
    u = random.random()
    ex = 1.0 / float(i.weight)
    i.nonce = math.pow(u, ex)

print("input : ", items)

items_out = sorted(items, key=lambda x: x.nonce, reverse=True)
print("output: ", items_out)