(25C) Sampling without repetition

[Albert Chan]

(04-27-2017 04:07 AM)nsg Wrote:  I wonder if it is possible to improve on the algorithm and generate a sample of modest k for arbitrary N,
for example, a sample of 30 out of 10000000.

Code:

import random
def randindex(k, n):
    s = [n] * k             # k samples
    for i in range(k):
        r = random.randrange(n-i)
        j = 0
        while r + j >= s[j]: j = j+1
        s[j+1:i+1] = s[j:i] # make room for s[j]
        s[j] = r + j        # sorted insert
    return s

Above code only need k random numbers, and return sorted samples.

>>> randindex(10,10) # no repeat
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

>>> random.seed(1)
>>> randindex(30,10000000)
[21060, 254459, 283474, 290410, 305901, 938595 ...