Re: Shuffling a linked list

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

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

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


.

Relevant Pages

  • Re: Constructing a random permutation on the fly
    ... I could put all the items in an array, shuffle them, and go through them from first to last, storing the shuffled array for as long as it's needed. ... i would like to avoid having to store great big lists of numbers if at all possible. ... Instead of storing the permutations, store, per user, a key to initialize the pseudo-random number generator that drives the shuffling, so you can re-generate that user's permutation when needed. ... three properties that for any fixed value of the key, the mapping between numbers is bijective, that mapping looks random, and that for different values of the key, the mapping looks different ...
    (sci.crypt)
  • Re: Constructing a random permutation on the fly
    ... This question is not really about cryptography, but it has a cryptographyish flavour, so i thought i'd ask it here. ... I could put all the items in an array, shuffle them, and go through them from first to last, storing the shuffled array for as long as it's needed. ... i would like to avoid having to store great big lists of numbers if at all possible. ... Construct the Cartesian product of the Galois fields; ...
    (sci.crypt)
  • 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)