StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>Neither of those is best. You need a Fisher-Yates shuffle. The problem with the random solution is that you do a lot of unnecessary work up front. The problem with the second solution is that the chances of duplicates becomes higher with time so that you're throwing away a lot of values.</p> <p>For a very efficient solution that gives you a subset of your values with <em>zero</em> possibility of duplicates (and no unnecessary up-front sorting), Fisher-Yates is the way to go.</p> <pre><code>dim n[N] // gives n[0] through n[N-1] for each i in 0..N-1: n[i] = i // initialise them to their indexes nsize = N // starting pool size do N times: i = rnd(nsize) // give a number between 0 and nsize-1 print n[i] nsize = nsize - 1 // these two lines effectively remove the used number n[i] = n[nsize] </code></pre> <p>By simply selecting a random number from the pool, replacing it with the top number from that pool, then reducing the size of the pool, you get a shuffle without having to worry about a large number of swaps up front.</p> <p>This is important if the number is high in that it doesn't introduce an unnecessary startup delay.</p> <p>For example, examine the following bench-check, choosing 10-from-10:</p> <pre><code><------ n[] ------> 0 1 2 3 4 5 6 7 8 9 nsize rnd(nsize) output ------------------- ----- ---------- ------ 0 1 2 3 4 5 6 7 8 9 10 4 4 0 1 2 3 9 5 6 7 8 9 7 7 0 1 2 3 9 5 6 8 8 2 2 0 1 8 3 9 5 6 7 6 6 0 1 8 3 9 5 6 0 0 5 1 8 3 9 5 2 8 5 1 9 3 4 1 1 5 3 9 3 0 5 9 3 2 1 3 9 1 0 9 </code></pre> <p>You can see the pool reducing as you go and, because you're always replacing the used one with an unused one, you'll never have a repeat.</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