Re: Random reordering of a list

From: jim clark (clark_at_uwinnipeg.ca)
Date: 11/08/04 

Date: Mon, 8 Nov 2004 13:46:18 -0600

Hi

On Sun, 7 Nov 2004, Top Spin wrote:

> If I need to shuffle a list of numbers and I have a decent random
> number generator, will the following algorithm do the job?
>
> Loop through the list. At each element, generate a random number, j,
> on (1,N) and swap the current element and element j.
>
> Do i=1 to n
> j=random(1,n)
> x=a(i)
> a(i)=a(j)
> a(j)=x
> End i
>
> If this does not result in true randomness, can someone explain why
> not and, even better, how to do it right (efficiently)?

In terms of your code, here would be one way that I have used
and learned (not sure from where) over the years. Essentially,
pick one element at random to occupy the last position, then one
from all but the last position for the second to last position,
and so on. I'm not sophisticated enough in this area to say
whether or why this approach might be better (or worse) than
yours.

do i = n to 2 step -1
  j = random(1,i)
  x = a(i)
  a(i) = a(j)
  a(j) = x
end i

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

  • Random reordering of a list
    ... If I need to shuffle a list of numbers and I have a decent random ... number generator, will the following algorithm do the job? ... Loop through the list. ...
    (sci.stat.math)
  • STL bind1st counterpart for unary function
    ... generator in the sense defined by SGI's online STL ... STL algorithm "generate". ... and just to avoid rolling my own loop to ...
    (comp.lang.cpp)
  • Re: Letter to US Sen. Byron Dorgan re unpaid overtime
    ... and Richard made it clear that he understands the order ... >> of evaluation of a for loop. ... > using strlen but using an Oalgorithm when there is a trivial O ... >> In most other languages the terminating ...
    (comp.programming)
  • Re: Efficiency questions: combined ifs and looping 4 times
    ... Choice of algorithm always has a far bigger impact in performance than ... Use sizeof before the loop, store the result in a var and use ... speaks well of PHP. ... your order of complexity analysis is off. ...
    (comp.lang.php)
  • Re: Agduria dungeon generation
    ... stage of the algorithm and rise appropriate error, ... A NTAE generator doesn't have to have any ... NTAE will happily accept all valid inputs and RNG states and produce ...
    (rec.games.roguelike.development)