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: 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)
  • 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)