Re: Shuffling a linked list
- From: CBFalconer <cbfalconer@xxxxxxxxx>
- Date: Fri, 29 Dec 2006 18:42:33 -0500
Richard Harter wrote:
.... snip ...
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.
With the extra pointer per node (O(n) space for the extra pointers)
there can be O(n) rand calls, zero data moves.
struct node {
struct node *next, *shuffling;
int used; /* a boolean */ /* probably unneeded */
struct data *datum;
};
struct node *deck, *shuffled;
and the only extra storage needed is for the pointers shuffling.
However the walks using next will be O(n*n). The act of shuffling
up can be combined with the act of dealing, and copying shuffled
into deck when deck becomes empty. With this autoshuffle dealing
need not worry about the deck size remaining (which provides very
nice opportunities for Blackjack players, except that they won't
know when the new deck is used, although they could figure it out
after enough deals).
--
Merry Christmas, Happy Hanukah, Happy New Year
Joyeux Noel, Bonne Annee.
Chuck F (cbfalconer at maineline dot net)
<http://cbfalconer.home.att.net>
.
- References:
- Shuffling a linked list
- From: A. Farber
- Re: Shuffling a linked list
- From: Pascal Bourguignon
- Re: Shuffling a linked list
- From: Richard Harter
- Re: Shuffling a linked list
- From: Googmeister
- Re: Shuffling a linked list
- From: Richard Harter
- Shuffling a linked list
- Prev by Date: Re: Shuffling a linked list
- Next by Date: Re: I need a super small program written
- Previous by thread: Re: Shuffling a linked list
- Next by thread: Re: Shuffling a linked list
- Index(es):
Relevant Pages
|
