Re: Random reordering of a list

From: jim clark (clark_at_uwinnipeg.ca)
Date: 12/05/04 

Date: Sun, 5 Dec 2004 16:29:15 -0600

Hi

On Sun, 5 Dec 2004, Top Spin wrote:
> My algorithm visits each element in the array in ascending order and
> swaps it with a random element in the entire array. I have simulated
> this algorithm with a few billion iterations and the distribution
> looks even.
>
> Jim Clark's algorithm also visits each element in the array except the
> first, but in reverse order, and he only swaps it with one of the
> unvisited elements. I was concerned that he doesn't explicitly visit
> the 1st element, but I also simulated this algorithm and the
> distribution also looks even.

It is not necessary to "visit" the last element because there is
nothing to switch it with when i = 1. For a forward version of
this, see: http://www.techuser.net/randpermgen.html, where the
following algorithm appears.

for (i=1 to n) ar[i] = i;
for (i=1 to (n-1)) swap(ar[i], ar[Random(i,n)]);

The first line seeds the array, and the second randomly inserts
values selected from higher positions starting at the first
position and working to the second from last.

Further related to this issue is the following message that
appears at:

http://www2.toki.or.id/book/AlgDesignManual/BOOK/BOOK4/NODE151.HTM

------------------------------------------
Generating random permutations is an important little problem
that people stumble across often, and often botch up. The right
way is the following two-line, linear-time algorithm. We assume
that Random[i,n] generates a random integer between i and n,
inclusive.

for i=1 to n do a[i] = i;
for i=1 to n-1 do swap[ a[i], a[ Random[i,n] ];

That this algorithm generates all permutations uniformly at
random is not obvious. If you think so, explain convincingly
why the following algorithm does not generate permutations
uniformly:

for i=1 to n do a[i] = i;
for i=1 to n-1 do swap[ a[i], a[ Random[1,n] ];

Such subtleties demonstrate why you must be very careful with
random generation algorithms. Indeed, we recommend that you try
some reasonably extensive experiments with any random generator
before really believing it. For example, generate 10,000 random
permutations of length 4 and see whether all 24 of them occur
approximately the same number of times. If you understand how
to measure statistical significance, you are in even better
shape.
---------------------------------------------

Note that the second algorithm (which the author says is
incorrect) randomly samples between 1 and n, rather than between
i and n as in the first algorithm (which the author says is
correct, and which is the forward version of the algorithm I
presented here ... I've long ago forgotten the source). If I
remember correctly, it may be that your algorithm corresponds to
part of this 2nd algorithm, although not in stopping at n-1. I'm
not sure if that makes a difference. And you did say that your
simulations showed your version to work properly (i.e., generate
each possible sequence equally often, p = 1/n!, presumably).

Best wishes
Jim

============================================================================
James M. Clark (204) 786-9757
Department of Psychology (204) 774-4134 Fax
University of Winnipeg 4L05D
Winnipeg, Manitoba R3B 2E9 clark@uwinnipeg.ca
CANADA http://www.uwinnipeg.ca/~clark
============================================================================

Relevant Pages

  • Re: An algorithm questions
    ... Mathieu Dutour -- Doubly linked list in two arrays + a array ... Richard Harter -- The devil's list algorithm ... The storage costs are: ... dependent; I prefer to use unsigned char arrays for that reason; YMMV. ...
    (comp.lang.c)
  • Re: regex question - trying to find ".mp3" in a SELECT box
    ... But `Array' is a Function object reference. ... Establish a new execution context using F's FormalParameterList, ... Since is not a primitive value, the exception should be thrown. ... | 5.2 Algorithm Conventions ...
    (comp.lang.javascript)
  • Re: Mergesort Vs Quicksort
    ... I might not have correctly remembered my algorithm of months ago ... for sorting records in an array using one auxilary of the ... on how things turn out from lower levels of recursion, ... whether the number of records in the array segment to be sorted is ...
    (comp.programming)
  • Re: Algorithmn for Creating All Permutations
    ... > Data belongs to two different groups- zero terminator or non-zero ... > idea if the array has 100 elements;-) ... > I need a general algorithm that will generate all possible permutations ...
    (borland.public.delphi.language.basm)
  • Re: Reference to derived type element by index?
    ... as a set of distinctively-named scalars. ... In another scope, the same common block ... would be a single array. ... algorithm and a specific application of the algorithm, ...
    (comp.lang.fortran)