Re: Shuffling a linked list

Oliver Wong wrote:
"A. Farber" <Alexander.Farber@xxxxxxxxx> wrote in message

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

Does anybody please have a good algorithm for me?

You have 2 lists: an input list and an output list. At the start
of the algorithm, your input list is of length 32, and your output
list is of length 0. At the end of the algorithm, your input list
will be length 0 and your output list will be length 32.

while(there are still cards in the input list) {
choose a card randomly from the input list.
Move that card to the tail of the output list.
}

That algorithm can be simplified by making the input list
circular. I also see no need for a doubly linked list, unless the
second link is used to form the output list in place.

--
Merry Christmas, Happy Hanukah, Happy New Year
Joyeux Noel, Bonne Annee.
Chuck F (cbfalconer at maineline dot net)
<http://cbfalconer.home.att.net>


.

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)
  • Re: Shuffling a linked list
    ... I have a doubly-linked list of 32 playing cards, ... Does anybody please have a good algorithm for me? ... linked lists. ... length n, randomly shuffle it using Ocalls to rand, Odata ...
    (comp.programming)