Re: Shuffling a linked list


Richard Harter wrote:
On 29 Dec 2006 10:46:31 -0800, "Googmeister" <googmeister@xxxxxxxxx>
wrote:


Richard Harter wrote:
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.

It can be done in O(n log n) with O(1) extra space, but your proposed
algorithm only does so if you assume the linked list has two pointers
per node (instead of the usual one).

The original statement was that the list was doubly linked. I quote:
"I have a doubly-linked list of 32 playing cards". I took that as a
given.

Yes, my mistake.

May I refine the challenge as follows: Given a singly linked list of
length n, randomly shuffle it using O(n) calls to rand, O(n log n) data
moves, and O(1) extra space.

You need at least n log n bits of randomness since there are n!
possible
outcomes and log n! ~ n log n. So, is it safe to assume each
call to rand() returns log n random bits?

.

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