Re: Shuffling a linked list

"A. Farber" <Alexander.Farber@xxxxxxxxx> writes:

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

Does anybody please have a good algorithm for me?

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.

Choose one random element in the list, remove it and put it in a new
list. Repeat until the original list is empty.

--
__Pascal Bourguignon__ http://www.informatimago.com/
In deep sleep hear sound,
Cat vomit hairball somewhere.
Will find in morning.
.

Relevant Pages

  • Re: Announcing my new Sci-fi Book
    ... your new TV won't be able to accept an analog signal from ... cheap credit you can't afford. ... recipients credit cards now. ... But I didn't move my head. ...
    (rec.arts.sf.written)
  • Re: Multiple Display Card
    ... Matrox G450 PCI 2 head display card. ... In the past, Scitech was working on a driver architecture that allowed multiple heterogenous video cards to function as an N-head display, but I haven't heard of progress being made on that in a while. ...
    (comp.os.os2.misc)
  • Re: New proposed DRM interface design
    ... >> should be no problem at all, this is what I consider a DRM ... one on each head. ... dualhead cards if a 3D window strattled both heads. ... send the line "unsubscribe linux-kernel" in ...
    (Linux-Kernel)
  • Re: Tournament Qs [LSJ]
    ... transparent sleeves b) plain opaque sleeves that look the same in either ... By placing HoN cards "updside down", ... "head over toes" yet, but you would if there are other already? ...
    (rec.games.trading-cards.jyhad)
  • Shuffling a linked list
    ... I have a doubly-linked list of 32 playing cards, ... (For several reasons I'm not using an array, ... last elements and I have 2 macros to insert an element at the ... I'd move that element at the "head" of the list. ...
    (comp.programming)