StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>Go through all the numbers m from 0 to N, deciding whether to include m in the set as encountered. You need to update the probability of including the next number based on the numbers already treated. </p> <p>Let's apply this idea to the example given, with n=3 and N=5. First consider m=0. There are 3 numbers remaining, and 5 possibilities, so 0 is in the set with probability 3/5. Use a random number generator to decide to include the number or not. Now consider m=1. If you included 0 in the set, then you have 2 numbers remaining and 4 possibilities, so it should be included with probability 2/4, but if 0 is not included, you have 3 numbers remaining and 4 possibilities and thus 1 should be included with probability 3/4. This continues until the required 3 numbers are included in the set.</p> <p>Here's an implementation in Python:</p> <pre><code>from __future__ import division import random def rand_set(n, N): nums_included=set() for m in range(N): prob = (n-len(nums_included)) / (N-m) if random.random() < prob: nums_included.add(m) return nums_included </code></pre> <p>You could (and probably should) add in a test to see when you've got enough numbers in your set, and break out of the loop early. </p> <p>The numbers are stored in a set, which varies in size from 0 to n, so the storage used is <code>O(n)</code>. Everything else uses constant space, so it's overall <code>O(n)</code>.</p> <p>EDIT Actually, you can go a little further with this approach, so that it takes constant space. In Python, just make a generator based on the above:</p> <pre><code>def rand_set_iter(n, N): num_remaining = n m = 0 while num_remaining > 0: prob = num_remaining / (N-m) if random.random() < prob: num_remaining -= 1 yield m m += 1 </code></pre> <p>Here, I've gone ahead and used a while loop instead of the for loop. To store the results, you'll of course need to use <code>O(n)</code> space. But if all you need to do is iterate through the numbers, the generator version does it in <code>O(1)</code>. </p> <p>For a language without generators, you can roll your own generator, calling a function repeatedly and updating a static or global variable.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload