[FIXED] Memory efficient version for the construction disjoint random lists

Issue

We have to positive integers b,n with b < n/2. We want to generate two random disjoint lists I1, I2 both with b elements from {0,1,...,n}. A simple way to do this is the following.

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

For large b,n (say b=100, n>1e7) the previous is not memory efficient. Since L is large. I am wondering if there is a method to get I1,I2 without using range(0,n+1)?

Solution

Here is a hit-and-miss approach which works well for numbers in the range that you mentioned:

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

For your problem, you could do something like:

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

Answered By - John Coleman