用于构造不连续随机列表的内存有效版本

Question

我们必须将b,n设为正整数b < n/2。我们想用I1, I2中的b个元素生成两个随机的不相交列表{0,1,...,n}.。一种简单的方法如下。

def disjoint_sets(bound,n):
    import random
    I1=[];I2=[];
    L = random.sample(range(0,n+1), n+1)
    I1 = L[0:bound]
    I2 = L[bound:2*bound]
    return I1,I2

对于大的b,n（例如b=100, n>1e7），前一个内存效率不高。由于L很大。我想知道是否有一种无需使用I1,I2即可获取range(0,n+1)的方法吗？

Answer 1

这是一种命中方法，对于您提到的范围内的数字非常有效：

import random

def rand_sample(k,n):
    #picks k distinct random integers from range(n)
    #assumes that k is much smaller than n
    choices = set()
    sample = []
    for i in range(k): #xrange(k) in Python 2
        choice = random.randint(0,n-1)
        while choice in choices:
            choice = random.randint(0,n-1)
        choices.add(choice)
        sample.append(choice)
    return sample

对于您的问题，您可以执行以下操作：

def rand_pair(b,n):
    sample = rand_sample(2*b,n)
    return sample[:b],sample[b:]