Re: Shuffling a linked list

From: "A. Farber" <Alexander.Far...@xxxxxxxxx>
I have a doubly-linked list of 32 playing cards, which I'd like
to randomly and evenly (!) shuffle.

Why only 32 instead of the usual 52? (Just curious.)

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

Without some additional API, such as a tool for removing an element
from somewhere, the task cannot be accomplished. Initially you have
32 cards in the list, and if you use either insert tool even once
you now have 33 cards in the list, and there's no way to ever get
back to 32.

I'm thinking of having an integer variable i which I'd increase
by one while going through my list. And if rand(i) < 1 then I'd
move that element at the "head" of the list. Which should give each
card a 1/32 possibility to land at the "head" position.

That requires ability to delete an element from one place (i) and
insert it somewhere else (head).

Nope. Try simulating that manually with just four cards (compute
probability of each possible outcome, then group the results per
who's at the head of the class, add within each group to get
subtotals, and compare them) and watch how the results aren't as
you had hoped. For example, the very last element you start with
has 1/n chance of ending at head (good) but (n-1)/n chance of
ending at bottom and no chance whatsoever of ending anywhere else.

Try this instead: Start with k0=0 k1=n. Generate rand(k1) and move
*that* element to the top of the list. Now increase k0 and decrease
k1, and compute the rand(k1) again, but skip the first k0 elements
and select randomly only from the remaining elements, i.e. move
element# k0 + rand(k1) to top. Each time you select from fewer
elements from the end of what you've already chosen (now topmost
segment) to the very end. When you're down to just one remaining
element not yet selected (k0=n-1 k1=1), you're done already.

Note that you can speed it up slightly by having two such linked
lists, one with the original data or a copy of it, out of which you
are removing random elements, and a second initially empty where
you are inserting the selected elements.

This takes on the order of n**2 steps (n times through main loop,
but in each loop nearly n steps down the list to find the element
to move, or nearly n/2 when using the two-list version), but for n
only 32 this should be fast enough if you do it only at the start
of each game. If n were really large, or you wanted to shuffle many
times per second, then I'd suggest a n*log(n) algorithm instead, or
better just use a damn array, which you need allocate only once.
.

Relevant Pages

  • Re: Opinions, please, on vocabulary flashcard organization
    ... The cards are much simpler. ... flashcards. ... criteria simultaneously, e.g. success rate, travel vocabulary, nouns ... - add functions to import/export/merge the flashcard lists. ...
    (alt.usage.english)
  • Re: Create-A-Clan Spoof Cards
    ... > of interesting cards to spoof (not necessarily just for combat decks) ... > while wandering through the lists: ...
    (rec.games.trading-cards.jyhad)
  • Re: scheme optimize question
    ... you're assuming that randomly shifting N+1 cards will yield ... lists and collecting data and putting it into a new form. ... Now that we have all the cards in order, we need to shuffle them. ... Let's come up with a sort function to do that. ...
    (comp.lang.scheme)
  • Re: MIA from Card list
    ... and a majority of us mail cards to them anyway - simply because we enjoy ... Please let us add you to our lists! ... of busy is probably nothing compared to many of you folks' busy. ... I *wish* Tak would share his address (hint hint) ...
    (rec.pets.cats.anecdotes)
  • OT: Christmas Ode to the Best/Worst Listers
    ... Twas three days until Christmas on alt.v.l-v, I'm reading the newsgroup ... The postman's delivered his now daily quota of cards from our clan scattered ... So I figured I'd put out my own little list of the posters I miss and the ... And billhere with lists here from winter through fall, ...
    (alt.vacation.las-vegas)