afew.py

from random import random

class Unreachable(Exception):
    pass

def chain(elem, poss):
    yield elem
    yield from poss

# (x, p)
def afew(poss, r):
    poss = iter(poss)
    precedes = [elem for _, elem in zip(range(r), poss)]
    if len(precedes) < r:
        return []

    z = sum(p for _, p in precedes)
    z = 1 - z

    choices = []
    while precedes:
        x, p = precedes.pop()
        z += p
        v = 0
        for x, p in chain((x, p), poss):
            pz = (p / z) / (1 - v / z)
            u = random()
            v += p
            if u < pz:
                choices.append((x, p))
                break
        else:
            raise Unreachable()
        z -= v

    return choices

def main():
    pass

if __name__ == '__main__':
    main()