Эффективная по памяти версия для построения непересекающихся случайных списков

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:]