usenet@cps3xx.UUCP (Usenet file owner) (05/17/89)
I need a fast algorithm to randomly rearrange the order of elements in
an array. Right now I am just using a random number generator to form
a list of numbers that directly determines the order of the array like this:
n = size of array
for i = 1 to n
{
do
x = random number between 1 and n
while x is not already in list[]
list[i] = x
}
The problem is that as the list fills up with numbers, the time spent in
the do loop getting a number not already in the list grows very large.
Does anyone know of a better way to do this? Any help would be greatly
appreciated!
Paul Reed
Internet: reedp@horus.cem.msu.edu Bitnet: reedp@MSUCEMlotto@midas.harvard.edu (Gerald I. Lotto) (05/17/89)
Any way you can randomize an array of indices will let you reorder the original array. One method that I like to use is to turn the array into 2 by n matrix. Fill array[n][2] with random numbers between 1 and m (m >> n), and sort "rows" by the "second column". Of course, it is much simpler in APL :-) -- Gerald Lotto - Harvard Chemistry Dept.
spl@mcnc.org (Steve Lamont) (05/18/89)
In article <3008@cps3xx.UUCP> reedp@frith.egr.msu.edu () writes: >I need a fast algorithm to randomly rearrange the order of elements in >an array. Right now I am just using a random number generator to form Table look up? -- spl Steve Lamont, sciViGuy EMail: spl@ncsc.org North Carolina Supercomputing Center Phone: (919) 248-1120 Box 12732/RTP, NC 27709
scotth@grebyn.COM (Scott Hutchinson) (05/18/89)
In article <3008@cps3xx.UUCP> reedp@frith.egr.msu.edu () writes: >The problem is that as the list fills up with numbers, the time spent in >the do loop getting a number not already in the list grows very large. > >Does anyone know of a better way to do this? Any help would be greatly >appreciated! How about filling the array initially with the numbers in order, then just doing random swaps. like: int i[100]; int j; for (j=0; j<100; j++) i[j]=j; for (j=0; j< some number of swaps; j++) swap(i[j],i[(j+j*2) % 100]) This seems like it should scramble the list. By the way, in case you don't know C, the % 100 is a modulo 100. -Scott Hutchinson -- ---------------------------------------------------------------------------- Standard Disclamers: These opinions are mine, they do not reflect on my Company at all. I can be reached at scotth@grebyn.com or scotth@grebyn.uucp
posert@ics.uci.edu (Bob Posert) (05/18/89)
In article <3008@cps3xx.UUCP> reedp@frith.egr.msu.edu () writes: >I need a fast algorithm to randomly rearrange the order of elements in >an array. [...] > n = size of array The algorithm I usually use is: {Get all numbers in the array} for i = 1 to N do a[i] = i endfor {Scramble them} for i = 1 to N do j = { random number, 1 <= j <= N } swap(a[i], a[j]); endfor -- Bob Posert I'm: posert@bonnie.ics.uci.edu or {sdcsvax|ucbvax}!ucivax!bonnie!posert
cook@cpsvax.cps.msu.edu (Tom Cook) (05/18/89)
In article <3008@cps3xx.UUCP> reedp@frith.egr.msu.edu () writes: >I need a fast algorithm to randomly rearrange the order of elements in >an array. Right now I am just using a random number generator to form >a list of numbers that directly determines the order of the array like this: > > n = size of array I usually use something like this: for i = n to 2 step -1 do begin x = random number between 1 and i swap array[i] and array[x] end This loop will always execute exactly n-1 times. >Paul Reed >Internet: reedp@horus.cem.msu.edu Bitnet: reedp@MSUCEM Tom Cook cook@cpsvax.msu.edu
yorick@nmsu.edu (Yorick Wilks) (05/18/89)
In article <LOTTO.89May17112504@midas.harvard.edu> lotto@midas.harvard.edu (Gerald I. Lotto) writes: One method that I like to use is to turn the array into 2 by n matrix. Fill array[n][2] with random numbers between 1 and m (m >> n), and sort "rows" by the "second column". i wasn't going to worry about this much until this bogus method appeared on the net. this method suffers from a bias toward original sort (modulo the stability of the sorting algorithm). the bias is small if m/n is large, but is always there. much better is to use the following algorithm which is adapted from knuth: /* shuffle the contents of an array... integers here, but they really could be anything */ shuffle(arr,n) int arr[]; int n; { /* walk along, inserting each element in a random place */ for (i=1;i<n;i++) { swap(arr[i],arr[random()%(i+1)]); } } of course it is difficult to do this in parallel, or in a single apl line, but at least it produces the correct result.
ahw@notecnirp.Princeton.EDU (Arthur Watson) (05/18/89)
In article <3008@cps3xx.UUCP> reedp@frith.egr.msu.edu () writes: >The problem is that as the list fills up with numbers, the time spent in >the do loop getting a number not already in the list grows very large. >Does anyone know of a better way to do this? Any help would be greatly >appreciated! Assume you have the array arr[0..MAX-1] filled with your unscrambled numbers. Now just do the following (with integer variables j and k): for j := 0 to MAX-1 do begin k := a random number between j and MAX-1 inclusive; swap arr[j] and arr[k]; end; This makes all scramblings equally likely, which you presumably want, (since for each array location you are selecting randomly among those elements not yet selected) and is the most efficient way to do so (since you only move each array element once [well, twice] :-)). -- Arthur Watson
dhesi@bsu-cs.bsu.edu (Rahul Dhesi) (05/18/89)
>fast algorithm to randomly rearrange the order of elements in >an array. /* array a[1..N] */ for (i = N; i > 1; i--) swap (a[i], a[rnd(i-1)]); /* need random no. in range 1..i-1 */ -- Rahul Dhesi <dhesi@bsu-cs.bsu.edu> UUCP: ...!{iuvax,pur-ee}!bsu-cs!dhesi
megauthier@watcgl.waterloo.edu (Marc E. Gauthier) (05/18/89)
In article <3008@cps3xx.UUCP> reedp@frith.egr.msu.edu () writes: >I need a fast algorithm to randomly rearrange the order of elements in >an array. Right now I am just using a random number generator to form >a list of numbers that directly determines the order of the array [...] Here's a simple way to do it in C: Object t, a[SIZE]; int i, j; /* this works by filling (backwards) the array with elements * picked randomly from the remaining ones at start of array */ for (i=SIZE-1; i>0; i--) { j = random() % i; /* return indice between 0 and i-1 */ t = a[i]; a[i] = a[j]; a[j] = t; } Hope it helps. It's a simple solution I always use to shuffle cards, etc. Marc -- Marc E. Gauthier megauthier@watcgl.waterloo.edu University of Waterloo
jmorton@daitc.daitc.mil (Joe Morton) (05/18/89)
In article <3008@cps3xx.UUCP> reedp@frith.egr.msu.edu () writes: >I need a fast algorithm to randomly rearrange the order of elements in >an array. Right now I am just using a random number generator to form >a list of numbers that directly determines the order of the array like this: > > n = size of array > > for i = 1 to n > { > do > x = random number between 1 and n > while x is not already in list[] > > list[i] = x > } I read this one in Byte quite a few years ago - I _may_ have used it once, and I unfortunately don't remember how well it worked. Now that the disclaimers have been dispensed with, here's the code: n = size of array for i = 1 to n { list[ i ] = i ; } for i = 1 to n { swap( list[ i ] , list[ random( n ) ] ) ; /* CALL BY REFERENCE */ } /* random( n ) returns random number between 1 and n */ If I'm guessing correctly, the original code is O(n^2) (or at least degenerates to worse) and the code above is O(n). The math for (1) is ugly, and I don't understand it very well, but I'll answer e-mail requests for how I arrived at that estimate. To complete the code, here's a really neat swap routine, in C: swap( a , b ) unsigned *a, *b; { *a ^= *b ; *b ^= *a ; *a ^= *b ; } Try it - it works! (for the non-C programmers, the Pascal equivalent to *a ^= *b is a := a xor b, and a and b are "var" parameters). Hope this helps. DISCLAIMER: Any code presented here is guaranteed to be as correct as anything you'd pay for. The opinions expressed here are not those of CDC or the DTIC-SPO.
abcscnge@csuna.csun.edu (Scott "The Pseudo-Hacker" Neugroschl) (05/18/89)
In article <3008@cps3xx.UUCP> reedp@frith.egr.msu.edu () writes:
]I need a fast algorithm to randomly rearrange the order of elements in
]an array. Right now I am just using a random number generator to form
]a list of numbers that directly determines the order of the array like this:
]
] n = size of array
]
] for i = 1 to n
] {
] do
] x = random number between 1 and n
] while x is not already in list[]
]
] list[i] = x
] }
]
list = array
N = size of list
for i from N down to 2 do
x = random number between 1 and i inclusive
swap list[i] and list[x]
end for
--
Scott "The Pseudo-Hacker" Neugroschl
UUCP: ...!sm.unisys.com!csun!csuna.csun.edu!abcscnge
-- Beat me, Whip me, make me code in Ada
-- Disclaimers? We don't need no stinking disclaimers!!!kwb@hpmtlx.HP.COM ($Keith_Blackwell@hpmtlkb) (05/19/89)
| I need a fast algorithm to randomly rearrange the order of elements in | an array. Right now I am just using a random number generator to form | a list of numbers that directly determines the order of the array like this: The easiest way is to just extract the components in random order. Set a "TopOfList" variable to the maximum index, then each time you need a new element you just take a random number between the lower index and TopOfList (inclusive) and swap that element with TopOfList, then decrement TopOfList. Of course, once you've run through the whole thing, the array has been randomly rearranged. And this is fast! I doubt you can do it any faster. I actually thought of this myself when in college, but then I found it in a slightly different form in (one of?) Knuth's algorithms books. I guess it's a pretty obvious idea. -- Keith Blackwell
leonard@bucket.UUCP (Leonard Erickson) (05/22/89)
In article <3008@cps3xx.UUCP> reedp@frith.egr.msu.edu () writes:
<I need a fast algorithm to randomly rearrange the order of elements in
<an array. Right now I am just using a random number generator to form
<a list of numbers that directly determines the order of the array like this:
<
< n = size of array
<
< for i = 1 to n
< {
< do
< x = random number between 1 and n
< while x is not already in list[]
<
< list[i] = x
< }
<
<The problem is that as the list fills up with numbers, the time spent in
<the do loop getting a number not already in the list grows very large.
<
<Does anyone know of a better way to do this? Any help would be greatly
<appreciated!
Yes. Do this:
n = sizeof of array
for i = 1 to n
x=random number from 1 to n
swap array[i] with array[x]
The idea is that what you want is _the arrray elements in a random order_
What you were doing was grabbing a random element of the array.
--
Leonard Erickson ...!tektronix!reed!percival!bucket!leonard
CIS: [70465,203]
"I'm all in favor of keeping dangerous weapons out of the hands of fools.
Let's start with typewriters." -- Solomon Short