Re: Shuffling a linked list
- From: "A. Farber" <Alexander.Farber@xxxxxxxxx>
- Date: 29 Dec 2006 14:46:02 -0800
Hi Robert,
Robert Maas, see http://tinyurl.com/uh3t wrote:
From: "A. Farber" <Alexander.Far...@xxxxxxxxx>
I have a doubly-linked list of 32 playing cards, which I'd like
to randomly and evenly (!) shuffle.
Why only 32 instead of the usual 52? (Just curious.)
it's a russian card game, similar to german skat:
http://en.wikipedia.org/wiki/Preferans
You probably get too many poker questions here in the group :-)
Without some additional API, such as a tool for removing an element
from somewhere, the task cannot be accomplished. Initially you have
32 cards in the list, and if you use either insert tool even once
you now have 33 cards in the list, and there's no way to ever get
back to 32.
Of course I have macros for removing and replacing elements too.
Try this instead: Start with k0=0 k1=n. Generate rand(k1) and move
*that* element to the top of the list. Now increase k0 and decrease
k1, and compute the rand(k1) again, but skip the first k0 elements
and select randomly only from the remaining elements, i.e. move
element# k0 + rand(k1) to top. Each time you select from fewer
elements from the end of what you've already chosen (now topmost
segment) to the very end. When you're down to just one remaining
element not yet selected (k0=n-1 k1=1), you're done already.
Hmm I think that will always move the lowest cards to much down...
Regards
Alex
--
http://preferans.de
.
- References:
- Shuffling a linked list
- From: A. Farber
- Re: Shuffling a linked list
- From: Robert Maas, see http://tinyurl.com/uh3t
- Shuffling a linked list
- Prev by Date: Re: Shuffling a linked list
- Next by Date: Re: Hash
- Previous by thread: Re: Shuffling a linked list
- Next by thread: Worst case execution time problem
- Index(es):
Relevant Pages
|
|
