StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>In <a href="http://en.wikipedia.org/wiki/Special:BookSources/978-0-201-89684-8" rel="noreferrer"><i>The Art of Computer Programming, Volume 2: Seminumerical Algorithms, Third Edition</i></a>, Knuth describes the following selection sampling algorithm:</p> <blockquote> <p>Algorithm S (Selection sampling technique). To select n records at random from a set of N, where 0 < n ≤ N.</p> <p>S1. [Initialize.] Set t ← 0, m ← 0. (During this algorithm, m represents the number of records selected so far, and t is the total number of input records that we have dealt with.)</p> <p>S2. [Generate U.] Generate a random number U, uniformly distributed between zero and one.</p> <p>S3. [Test.] If (N – t)U ≥ n – m, go to step S5.</p> <p>S4. [Select.] Select the next record for the sample, and increase m and t by 1. If m < n, go to step S2; otherwise the sample is complete and the algorithm terminates.</p> <p>S5. [Skip.] Skip the next record (do not include it in the sample), increase t by 1, and go back to step S2.</p> </blockquote> <p>An implementation may be easier to follow than the description. Here is a Common Lisp implementation that select n random members from a list:</p> <pre><code>(defun sample-list (n list &optional (length (length list)) result) (cond ((= length 0) result) ((< (* length (random 1.0)) n) (sample-list (1- n) (cdr list) (1- length) (cons (car list) result))) (t (sample-list n (cdr list) (1- length) result)))) </code></pre> <p>And here is an implementation that does not use recursion, and which works with all kinds of sequences:</p> <pre><code>(defun sample (n sequence) (let ((length (length sequence)) (result (subseq sequence 0 n))) (loop with m = 0 for i from 0 and u = (random 1.0) do (when (< (* (- length i) u) (- n m)) (setf (elt result m) (elt sequence i)) (incf m)) until (= m n)) result)) </code></pre>

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