Re: Shuffling a linked list

A. Farber said:

Hello,

I have a doubly-linked list of 32 playing cards, which I'd like to
randomly and evenly (!) shuffle.

(For several reasons I'm not using an array, which I could go
through once, keeping swapping cards at random positions.)

I have a list head with 2 pointers - to the very 1st and to the
last elements and I have 2 macros to insert an element at the
"head" or at the "tail".

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

--
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: list of numbers in randomised order - prg. struggles at large (~10^5) numbers
    ... Here's a fairly simple yet efficient algorithm for shuffling lists, ... should produce a perfect shuffle. ... (let (heads tails) ... (push item heads) ...
    (comp.lang.lisp)
  • Re: list of numbers in randomised order - prg. struggles at large (~10^5) numbers
    ... based on a post from comp.lang.functional by Ben Rudiak-Gould. ... should produce a perfect shuffle. ... I have a hard time understanding the above let-dolist combination, but looking at the Haskell implementation in the referenced posting, it is not guaranteed to terminate. ... However, the runs should tend to use about n*logcoin-flips, considering that the splitting into two sublists is most likely to result in nearly equally long lists. ...
    (comp.lang.lisp)
  • Re: Similar random-number query (TI-83 Basic)
    ... > I'm trying to shuffle a list of 52 elements in TI-83 Basic. ... > canonical implementation of this (AFAIK) is to create a second list ... > of 52 random floating-point values, and then sort the two lists in ... (The sort itself is pretty fast.) ...
    (comp.programming)
  • Re: randomly generate n of each of two types
    ... If you really care about shuffling large lists, you can chain PRNGs. ... instance, you might use shuffle() to generate a random batch of items, ... yield valuelist ...
    (comp.lang.python)
  • Re: Shuffling a linked list
    ... I have a doubly-linked list of 32 playing cards, ... randomly and evenly shuffle. ... Just use the standard shuffling algorithm, mildly adapted for lists. ... Point one of your pointers, P1, to the first unprocessed item in the list, ...
    (comp.programming)