Re: Shuffling a linked list

Richard Harter said:

On Fri, 29 Dec 2006 20:52:43 +0000, Richard Heathfield
<rjh@xxxxxxxxxxxxxxx> wrote:

<snip>

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.)

Given the small actual value of n (32) that's probably as good as
anything. However it's O(n**2).

I nearly disagreed, but of course you're right - it comes from bumping P2
along the list to find the Rth element, once per iteration. Blech. Okay, I
withdraw the suggestion.

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

Relevant Pages

  • Re: Interesting article by Joel Spolsky: The Perils of JavaSchools
    ... >>>linked lists. ... However I should have included the sites definition of ... >I can image I'd have been jumped on, and I am not sure this reference ... Richard Harter, cri@xxxxxxxx ...
    (comp.programming)
  • Re: Introsort
    ... Richard Harter wrote: ... >>I'm having trouble finding information on the web. ... > Try searching google on ... What I've found seems to be talking about lists ...
    (comp.programming)
  • Re: very strange pthread problem
    ... The worker threads need access to a class member function or two. ... STL vector so each index into the vector points to the list of pointers ... it's just storing the pointers to the STL lists and the vector ... Then I moved the whole thing to a single cpu Linux ...
    (comp.programming.threads)
  • Re: Strange behavior with iterables - is this a bug?
    ... was exactly for large large lists:) Unnecessary in this example, ... Gary Herron wrote: ... The first bit opens each file but uses multiple times. ... and then iterate through the list as you wish. ...
    (comp.lang.python)
  • Re: Implementing Lisp in C?
    ... What I did was to pack the pointers ... it meant bigger header blocks on boxed objects, ... Whenever the "to-visit" list becomes empty, ... both the garbage and to-visit lists are empty, ...
    (comp.lang.lisp)