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 <tom@securescience.net>
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
>permutation.

Huh?

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
http://home.ecn.ab.ca/~jsavard/index.html

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. ...
(Fedora)
• 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, ...
(rec.arts.sf.written)
• Re: UUIDs on drives
... along with a number of other partitions. ... I just ran top and my swap ... (identified by UUID) ... My mistake. ...
(Ubuntu)
• 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 ...
(sci.math)
• 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? ...
(microsoft.public.vb.general.discussion)