Re: Shuffling a linked list

A. Farber said:

Hi,

Richard Heathfield wrote:
Just use the standard shuffling algorithm, mildly adapted for lists.

Point one of your pointers, P1, to the first unprocessed item in the
list, item I. (There are 32 - I unprocessed items.) Pick a random number
in the range 1 to 32 - I. Counting the item pointed to by P1 as 1, keep
counting along the list, using P2 to point, until you hit the random
number you generated. Swap the data at P1 with the data at P2. Now move
P1 to point to the next item on the list. Iterate until done. (When P1 is
NULL - because it fell off the end of the list - you're done.)

thank you, I'll probably do that.

No, you probably won't, since it's O(n^2), unlike its array equivalent, as
Richard Harter correctly points out.


Even though the O'Reilly book "Perl Cookbook" states
in the chapter "Picking a Random Line from a File" that
swapping elements isn't evenly random (sorry don't have
the text right now)

Well, the algorithm is about as evenly random as you're going to get. The
book is probably talking about a slightly different method, in which you
swap N arbitrary pairs chosen from the entire array, and that does indeed
introduce significant imbalances, which the method I gave does not.

But if all you want to do is pick *one* line at random from a file, it's
easy and you don't need a list.

Read the first line, and keep it.
While you succeeded in reading another line, the Nth:
Roll an N-sided die.
If you score 1, keep the new line instead of the old one.
Endwhile

Seeing why this works properly is left as an exercise.

--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at the above domain, - www.
.