Matthew C. Clarke <·······@unpsun1.cc.unp.ac.za> writes:
This algorithm is pretty obvious, but if you use it, please acknowledge
that I wrote it. If you sell it at a profit, I want a share.
You need a random number generator.
First represent the cards as e.g. [card(1,h), card(2,h), card(3,h), ...
card(j,h), card(q,h), card(k,h), card(1,d), card(2,d), card(3,d), ...
card(1,c), card(2,c), card(1,s), card(2,s)]
Then assign each a random number e.g.
[0.2314-card(1,h), 0.6341-card(2,h), 0.3101-card(3,h), ... ]
Keysort that list and your cards are shuffled.
If you are dealing with cards that are replaced instead of being dealt
to exhaustion, or with drawing a single card from a pack and replacing
it before drawing the next, there is a simpler way. Generate a random
integer in the range 1-13 to determine the value and another 1-4 to
determine the suit of the card.
Ken Johnson
--
I'd rather be EATING! # Ken Johnson
# +44 31 650 3799
# Business Studies
# Edinburgh University
A simple card shuffling algorithm that is linear in the number of
cards is:
Represent the cards as an array of length N. We will use 52.
remove-random-card(array,num-cards-left)
card-to-pick = randum(0,num-cards-left)
switch(array[card-to-pick],array[num-cards-left])
num-cards-left = num-cards-left - 1
return array[num-cards-left]
Then call it like
cards-left = 52
while (cards-left > 0)
deal(remove-random-card(deck,cards-left))
Gary
In article <··········@festival.ed.ac.uk> ···@festival.ed.ac.uk (K Johnson) writes:
I don't understand Lisp, so forgive my checking that I understand what
you mean. Are you doing this:
int i;
char (*card)[] = {"1H", "2H", ... "QS", "KS"}; /* ordered cards */
#define NCARDS (sizeof(card)/sizeof(char *)) /* No of cards */
char (*deck)[NCARDS]; /* rearranged cards */
for (i = 0; i < NCARDS; ++i)
{
deck[random_integer(NCARDS)] = card[i];
}
In which case the problem is that random_integer( ) will sometimes
return a number that it has returned already, and some elements of deck
will be garbage. The only way I can see to fix this is to make a note
of all the numbers that random_integer( ) has returned, and if a number
is returned twice you keep on generating random numbers until you get
one that has not been returned before. This will take O(n^2) time I
think.
No need to make note of numbers already returned.
All one needs to do is keep an array with entries 1--52 in arbitrary
order.
Generate first, a random integer k_1 between 1 and 52 (inclusive),
exchange entry k_1 and entry 52.
Then generate another random integer k_2 between 1 and 51. Exchange entry
k_2 and entry 51.
And so on till the effective size is 1.
--
---
B. Narasimhan ·····@euler.bd.psu.edu
Division of Science
Penn State Erie, The Behrend College
Erie, PA 16563-0203
From: Ian G Batten
Subject: Re: WANTED: Card shuffling algorithm
Date:
Message-ID: <CLoBE2.4Ln@fulcrum.co.uk>
In article <···················@euler.bd.psu.edu>,
Balasubramanian Narasimhan <·····@euler.bd.psu.edu> wrote:
> All one needs to do is keep an array with entries 1--52 in arbitrary
> order.
There's some code that I wrote many years ago in the cookie1.el file in
the Emacs 19 distribution. I have a feeling that it's wrong, now I come
to look at it seven years later.
For an array A of N elements, numbered 0..(N-1), each element A[i] is
exchanged with A[j], where j is in the range [i, N). Should j just be a
random element, rather than an element ``after'' i?
(defun shuffle-vector (vector)
"Randomly permute the elements of VECTOR (all permutations equally likely)"
(let ((i 0)
j
temp
(len (length vector)))
(while (< i len)
(setq j (+ i (random (- len i))))
(setq temp (aref vector i))
(aset vector i (aref vector j))
(aset vector j temp)
(setq i (1+ i))))
vector)
In article <··········@fulcrum.co.uk>, Ian G Batten <···@fulcrum.co.uk> wrote:
>For an array A of N elements, numbered 0..(N-1), each element A[i] is
>exchanged with A[j], where j is in the range [i, N). Should j just be a
>random element, rather than an element ``after'' i?
No. The simplest way to see that is to count the number of possible
choices.
Seth
Isn't random shuffling fully discussed in Knuth vol. 2?
(D.E.Knuth, The Art of Computer Programming, vol. 2, Seminumerical Algorithms,
Addison-Wesley, 2nd edition, circa 1980).
Sorry, I previously posted this under the wrong title.
Robert Hill
"Though all my wares be trash, my heart is true."
- John Dowland, Fine Knacks for Ladies (1600)
From article <······················@leeds.ac.uk>, by ·····@sun.leeds.ac.uk (Robert Hill):
>
>Isn't random shuffling fully discussed in Knuth vol. 2?
>
>(D.E.Knuth, The Art of Computer Programming, vol. 2, Seminumerical Algorithms,
> Addison-Wesley, 2nd edition, circa 1980).
There's a very concise dicussion of this topic, and also selecting random
subsets, in one of Jon Bentley's _Programming Pearls_ books (vol. 2, I
think). More than a little easier to follow than Knuth.
Persi Diaconis is probably the authority on this topic. A popular
article reported on his analysis of card shuffling, but I forget the
reference. The main conclusion, if I remember it well, was that
one need to use at least 7 riffle shuffles.
Here are some references that I found using the Cumulative Index to
Statistics.
%AUTHOR = Dave Bayer
%AUTHOR = Persi Diaconis
%TITLE = Trailing the dovetail shuffle to its lair
%JOURNAL = Ann. of Appl. Probability
%VOLUME = 2
%PAGES = 294-313
%YEAR = 1992
%KEYWORDS = Probability; Gambling
%AUTHOR = David Aldous
%AUTHOR = Persi Diaconis
%TITLE = Shuffling cards and stopping times
%JOURNAL = Amer. Math'l. Monthly
%VOLUME = 93
%PAGES = 333-348
%YEAR = 1986
%KEYWORDS = Random walk
%AUTHOR = Simo Puntanen
%TITLE = Shuffling cards
%JOURNAL = Teaching Stat.
%VOLUME = 13
%PAGES = 28-31
%YEAR = 1991
%KEYWORDS = Computing
%AUTHOR = L. Flatto
%AUTHOR = A. M. Odlyzko
%AUTHOR = D. B. Wales
%TITLE = Random shuffles and group representations
%JOURNAL = Ann. of Probability
%VOLUME = 13
%PAGES = 154-178
%YEAR = 1985
%AUTHOR = John W. Rosenthal
%TITLE = Card Shuffling
%JOURNAL = Math. Magazine
%VOLUME = 54
%PAGES = 64-67
%YEAR = 1981
%AUTHOR = Edward O. Thorp
%TITLE = Nonrandom shuffling with applications to the game of Faro
%JOURNAL = J. of the Amer. Stat'l. Assn.
%VOLUME = 68
%PAGES = 842-847
%YEAR = 1973
%KEYWORDS = Gambling; Blackjack
%AUTHOR = Gary Gottlieb
%TITLE = Non-random shuffling for multiple decks
%JOURNAL = J. of Appl. Probab.
%VOLUME = 24
%PAGES = 402-410
%YEAR = 1987
%KEYWORDS = Brownian bridge; Gambling
%AUTHOR = Steve Medvedoff
%AUTHOR = Kent Morrison
%TITLE = Groups of perfect shuffles
%JOURNAL = Math. Magazine
%VOLUME = 60
%PAGES = 3-14
%YEAR = 1987
%KEYWORDS = Games
%AUTHOR = P. Glaister
%TITLE = Card shuffling -- A micro computer approach
%JOURNAL = Math. and Computer Educ., The MATYC J., Inc.
%VOLUME = 24
%PAGES = 7-10
%YEAR = 1990
%KEYWORDS = Teaching
--
---
B. Narasimhan ·····@euler.bd.psu.edu
Division of Science
Penn State Erie, The Behrend College
Erie, PA 16563-0203
An interesting related problem is selecting a random element from
a list of unknown length (i.e. you have the start of a list but
don't have a count). You simply select the first element, then
select the second element with a chance of 1/2, the next with a
chance of 1/3, etc. This is from Rogue source code. It is probably
not very efficient for longer lists, assuming your random number
generator is more expensive than 1 or 2 next-element hops.
---
Merlyn LeRoy
Balasubramanian Narasimhan (·····@euler.bd.psu.edu) wrote:
: Persi Diaconis is probably the authority on this topic. A popular
: article reported on his analysis of card shuffling, but I forget the
: reference. The main conclusion, if I remember it well, was that
: one need to use at least 7 riffle shuffles.
: Here are some references that I found using the Cumulative Index to
: Statistics.
There's one algorithm that hasn't been mentioned yet -- it's basically
an inverse of the 'Bogosort' algorithm. In a Bogo-sort, you take a deck
in some random order and throw it up in the air repeatedly until it
lands in some particular order.
So if you have cards which are already in some known order, you simply
toss them in the air repeatedly until they land in a 'random' order.
[big-time ;-)]
--
\\|//
- - "Dyslexics UNTIE! Dyslexics LURE!!"
o o -- Elbo Room ex-graffito
J roberto sierra
O tempered microdesigns NOTICE:
\_/ san francisco, ca The ideas and opinions expressed
····@netcom.com herein are not those of the author.
In article <··········@festival.ed.ac.uk>, ···@festival.ed.ac.uk (K Johnson) writes:
|> ····@CS.CMU.EDU (Garrett Pelton) writes:
|>
|> >A simple card shuffling algorithm that is linear in the number of
|> >cards is:
|>
|> >Represent the cards as an array of length N. We will use 52.
|>
|>
|> > remove-random-card(array,num-cards-left)
|> > card-to-pick = randum(0,num-cards-left)
|> > switch(array[card-to-pick],array[num-cards-left])
|> > num-cards-left = num-cards-left - 1
|> > return array[num-cards-left]
|>
|>
|> I don't understand Lisp, so forgive my checking that I understand what
|> you mean. Are you doing this:
|>
|> int i;
|> char (*card)[] = {"1H", "2H", ... "QS", "KS"}; /* ordered cards */
|> #define NCARDS (sizeof(card)/sizeof(char *)) /* No of cards */
|> char (*deck)[NCARDS]; /* rearranged cards */
|>
|> for (i = 0; i < NCARDS; ++i)
|> {
|> deck[random_integer(NCARDS)] = card[i];
|> }
|>
The code I gave was not in any particular language.
The key difference between the code I gave and the code you used
was the switch. This moves the card that is dealt away so it is not
dealt again. Modifying your code to do this gives us:
int i;
char (*card)[] = {"1H", "2H", ... "QS", "KS"}; /* ordered cards */
#define NCARDS (sizeof(card)/sizeof(char *)) /* No of cards */
char (*deck)[NCARDS]; /* rearranged cards */
for (i = NCARDS; i ;)
{
deck[i] = get_random_card(card,&i);
}
char *get_random_card(char *cards[],int *num_cards)
{
int card_picked;
char *temp;
card_picked = random_integer(*num_cards);
temp = cards[card_picked];
cards[card_picked] = cards[num_cards];
cards[num_cards] = temp;
num_cards --;
return cards[num_cards+1];
}
This picks a card moves it to the last position, then decrements
the number of cards before returning the card at the end (that was
picked). Since the bound on the random integer is always the number
of cards available, and every card picked is moved to a position
greater than the number of cards available, a card cannot be picked
twice. This only goes through the array once, and does a constant
amount of processing for each element. It is O(n).
In which case the problem is that random_integer( ) will sometimes
|> return a number that it has returned already, and some elements of deck
|> will be garbage. The only way I can see to fix this is to make a note
|> of all the numbers that random_integer( ) has returned, and if a number
|> is returned twice you keep on generating random numbers until you get
|> one that has not been returned before. This will take O(n^2) time I
|> think.
|>
|> Ken Johnson
|>
|>
|> --
|> I'd rather be EATING! # Ken Johnson
|> # +44 31 650 3799
|> This .signature was funded by the Rural .Sig # Business Studies
|> Development Fund of the European Community # Edinburgh University