Re: Help: Randomizing a List of Numbers

From: John Savard (jsavard_at_excxn.aNOSPAMb.cdn.invalid)
Date: 07/20/04

Date: Tue, 20 Jul 2004 12:36:28 GMT

On Tue, 20 Jul 2004 10:07:46 GMT, Tom St Denis <>
wrote, in part:

>Your other post about doing the "swaps" is exactly what I was talking
>against. It's not provably going to get you a uniformly distributed


As long as you don't make the mistake of doing the swap between the
item in the list that you're trying to fill permanently, and one of
the locations *already* filled, of course the algorithm I exhibited
provides a uniformly distributed permutation from the space of 10,000!
possibilities. The side effect of shifting around the unallocated
items so as to avoid moving them a lot does not change the fact that
each one still has an equal opportunity of being selected.

The "swap" is *precisely* the optimization required.

John Savard

Relevant Pages

  • Re: iptables fubared?
    ... Huh, weirdly I didn't see any of these messages until the last one. ... Or maybe someone replied privately by mistake? ... But inetd or tcp-server could also be used. ...
  • Re: Socialism in SF
    ... :: theoretical physics, ... : plausible prose man ... Huh, what is that a problem with, then? ... You seriously can't tell the difference between a mistake in calculation, ...
  • Re: UUIDs on drives
    ... along with a number of other partitions. ... I just ran top and my swap ... (identified by UUID) ... My mistake. ...
  • Re: How to prove that a random sort algorithm converges?
    ... I randomly select a pair of two numbers at adjacient poisitions, ... and I swap their position if the value at position i is ... The rest wasn't affected by that mistake, simply because the rest had the ...
  • Re: MDI with Scrollbars
    ... I was in a time crunch and wanted to get an opinion. ... upfront how to test the problem, it was my mistake not to do the work. ... HUH? ...