Weighted Random Sampling

#!/usr/bin/python

import random
import bisect

weights = None
orig_weights = None

def wrs(items, sample_size):
    global weights
    global orig_weights

# Initialize the weights on the first invocation.
    if not weights:
        weights = [i[0] for i in items]
        orig_weights = list(weights) # full copy
    values = [i[1] for i in items]

# Yield sample_size samples.
    for i in range(sample_size):
        # Calculate cumulative list of weights.
        total_weight = 0
        cumulative_weights = []
        for i in range(len(items)):
            total_weight += weights[i]
            cumulative_weights.append(total_weight)

# Pick a random value in [0, total_weight).
        rnd = random.random() * total_weight

# Use bisect to locate item index.
        idx = bisect.bisect(cumulative_weights, rnd)

# Decrement weight of picked item.
        weights[idx] -= 1

# Reset weights when their sum reaches zero.
        if sum(weights) <= 0:
            weights = list(orig_weights) # full copy

# Yield value corresponding to item index.
        yield values[idx]

def main(iterations=10000, sample_size=3):
    assert iterations >= 1
    assert sample_size >= 1
    items = [
            ( 5, 'a'),
            (10, 'b'),
            (20, 'c'),
            (30, 'd'),
            (35, 'e'),
    ]

# Dictionary of item hitcounts.
    result = dict(zip([i[1] for i in items], [0] * len(items)))

# Dictionary of size-of-result-set hitcounts.
    lresult = dict(zip(range(1, sample_size+1), [0] * sample_size))

for i in range(iterations):
        result_set = set(wrs(items, sample_size))
        lresult[len(result_set)] += 1
        result[random.choice(list(result_set))] += 1

print 'Distribution of results:'
    print '\n'.join(['  %s: %6d %5.3f' % \
            (k, result[k], float(result[k])/iterations) for k in sorted(result)])
    print '\n'
    print 'Distribution of result set size:'
    print '\n'.join(['  %s: %6d %5.3f' % \
            (k, lresult[k], float(lresult[k])/iterations) for k in sorted(lresult)])

if __name__ == '__main__':
    import sys
    if len(sys.argv) >= 3:
        main(iterations=int(sys.argv[1]), sample_size=int(sys.argv[2]))
    else:
        main()

Python Fiddle

Python Cloud IDE