Re: Shuffling a linked list

On Fri, 29 Dec 2006 18:07:16 +0100, Pascal Bourguignon
<pjb@xxxxxxxxxxxxxxxxx> wrote:

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

Probably the simplest method is use an auxilliary array, put the cards
in it, use the standard O(n) shuffling algorithm, and relink the cards
into a doubly-linked list. All steps are O(n) and the code is simple in
each step.


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.

As stated, this doesn't make a lot of sense - all it would do is reverse
the list. Even if you have a changing epsilon(i) with a test rand(i) <
epsilon(i) it still wouldn't work. Consider, for example, the last
element in the list. In your scheme it could end up as the first
element or the last element but never anywhere inbetween.

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

That won't quite do because you haven't specified how you find to find
the one random element. The obvious method is to traverse the list a
random distance. That will produce an O(n**2) algorithm. Given the
shortness of the list (32) that may well be acceptable but I wouldn't
exactly call it a good algorithm.

This is an interesting problem if we have the constraint that there is
no extra storage to be used. It obviously can be done in O(n * log n)
by converting the list into a balanced tree and then randomly extracting
elements one at a time. I don't think that there is an O(n) algorithm -
if there were you could use it to do constant time random accesses into
linked lists.

There may well be a more elegant O(n*log n) algorithm but doesn't occur
to me offhand.


.

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: Shuffling a linked list
    ... I have a doubly-linked list of 32 playing cards, ... card a 1/32 possibility to land at the "head" position. ... lists, one with the original data or a copy of it, out of which you ... or you wanted to shuffle many ...
    (comp.programming)
  • Re: Shuffling a linked list
    ... I have a doubly-linked list of 32 playing cards, ... randomly and evenly shuffle. ... Does anybody please have a good algorithm for me? ... linked lists. ...
    (comp.programming)
  • 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)