Path: csiph.com!v102.xanadu-bbs.net!xanadu-bbs.net!feeder.erje.net!eu.feeder.erje.net!newsfeed.freenet.ag!news2.euro.net!newsgate.cistron.nl!newsgate.news.xs4all.nl!post.news.xs4all.nl!not-for-mail
To: python-list@python.org
From: Peter Otten <__peter__@web.de>
Subject: Re: Multiple disjoint sample sets?
Date: Sun, 13 Jan 2013 11:16:03 +0100
Organization: None
References: <roy-7E69C0.09152911012013@news.panix.com>
Mime-Version: 1.0
Content-Type: text/plain; charset="ISO-8859-1"
Content-Transfer-Encoding: 7Bit
User-Agent: KNode/4.7.3
Precedence: list
Newsgroups: comp.lang.python
Message-ID: <mailman.464.1358072165.2939.python-list@python.org>
Lines: 57
NNTP-Posting-Host: 2001:888:2000:d::a6
Xref: csiph.com comp.lang.python:36728

Roy Smith wrote:

> I have a list of items.  I need to generate n samples of k unique items
> each.  I not only want each sample set to have no repeats, but I also
> want to make sure the sets are disjoint (i.e. no item repeated between
> sets).
> 
> random.sample(items, k) will satisfy the first constraint, but not the
> second.  Should I just do random.sample(items, k*n), and then split the
> resulting big list into n pieces?  Or is there some more efficient way?
> 
> Typical values:
> 
> len(items) = 5,000,000
> n = 10
> k = 100,000

I would expect that your simple approach is more efficient than shuffling 
the whole list. 

Assuming there is a sample_iter(population) that generates unique items from 
the population (which has no repetitions itself) you can create the samples 
with

g = sample_iter(items)
samples = [list(itertools.islice(g, k) for _ in xrange(n)]

My ideas for such a sample_iter():

def sample_iter_mark(items):
    n = len(items)
    while True:
        i = int(random()*n)
        v = items[i]
        if v is not None:
            yield v
            items[i] = None

This is destructive and will degrade badly as the number of None items 
increases. For your typical values it seems to be OK though. You can make 
this non-destructive by adding a bit array or a set (random.Random.sample() 
has code that uses a set) to keep track of the seen items.

Another sample_iter() (which is also part of the random.Random.sample() 
implementation):

def sample_iter_replace(items):
    n = len(items)
    for k in xrange(n):
        i = int(random()*(n-k))
        yield items[i]
        items[i] = items[n-k-1]

You can micro-optimise that a bit to avoid the index calculation. Also, 
instead of overwriting items you could swap them, so that no values would be 
lost, only their initial order.