Re: Shuffling a linked list

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. However, yes, you can do it in O(n log n) with O(1) extra space
and a singly linked list by doing a mergesort with a random compare.
That's pretty. OTOH it does require O(n log n) calls to rand whereas
using a tree only requires O(n) calls to rand.

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

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.



.

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: linked list
    ... One single pass algorithm would be to use a five element circular buffer ... After all, in today's processors, L1 and L2 cache ... are many times faster than main memory, and linked lists are notorious for ...
    (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)