Beginner Question--rand( )

[hedylogus]

I've just begun learning C++ and I'm trying to write a program to shuffle a
deck of cards. I've succeeded....fo r the most part....but every now and
then rand() produces duplicate random numbers causing me to "lose" a card.
How do I avoid this??? I've attached my code below for reference. Thanks
in advance.

------------------------
#include <iostream>
#include <cstdlib>
#include <ctime>
#include <string>
#include <map>
#include <algorithm>

using namespace std;

string cardDeck[] = {"As", "Ah", "Ad", "Ac",
"2s", "2h", "2d", "2c",
"3s", "3h", "3d", "3c",
"4s", "4h", "4d", "4c",
"5s", "5h", "5d", "5c",
"6s", "6h", "6d", "6c",
"7s", "7h", "7d", "7c",
"8s", "8h", "8d", "8c",
"9s", "9h", "9d", "9c",
"Ts", "Th", "Td", "Tc",
"Js", "Jh", "Jd", "Jc",
"Qs", "Qh", "Qd", "Qc",
"Ks", "Kh", "Kd", "Kc"};

map<int,string> shuffledDeck;
int randomNumber[52]; //used for debug purposes

int main()
{
srand( time(NULL) );

cout << "Current seed value: "
<< time(NULL)
<< "\n\n";

for (int i=0; i<52; ++i)
{
randomNumber[i] = rand();
shuffledDeck[ randomNumber[i] ] = cardDeck[i];
}

for (map<int,string >::iterator p = shuffledDeck.be gin(); p !=
shuffledDeck.en d(); ++p)
{
cout << p->first
<< "\t"
<< p->second
<< endl;
}

if (shuffledDeck.s ize () != 52) //indicates duplicate random numbers
{
sort(randomNumb er, randomNumber+52 ); //easy viewing
cout << endl
<< "DUPLICATE RANDOM NUMBERS!\n\n";
for (int i=0; i<52; ++i)
cout << randomNumber [i]
<< "\t";

cout << "\n";
}

cout << endl;
system("PAUSE") ;
return 0;
}

[Pete Becker]

hedylogus wrote:

every now and
then rand() produces duplicate random numbers
Of course it does. If it didn't, the numbers wouldn't be random.
How do I avoid this???

std::random_shu ffle.

--

"To delight in war is a merit in the soldier,
a dangerous quality in the captain, and a
positive crime in the statesman."
George Santayana

"Bring them on."
George W. Bush

[Cy Edmunds]

"Pete Becker" <pe********@acm .org> wrote in message
news:3F******** *******@acm.org ...

hedylogus wrote:

every now and
then rand() produces duplicate random numbers
Of course it does. If it didn't, the numbers wouldn't be random.

Repeat values are a consequence of finite numbers of bits computed by the
algorithm, not randomness itself. Of course with certain lousy
implementations of rand() only a miserly 15 bits (the absolute minimum
allowed by the standard) are provided, resulting in repetition in very short
run lengths.

How do I avoid this???

std::random_shu ffle.

Or get a decent random number generator (31 bits or more). They are readily
available. You will still get repeats if you let your program run for the
rest of your life.

--
Cy
http://home.rochester.rr.com/cyhome/

[Buster Copley]

Cy Edmunds wrote:

"Pete Becker" <pe********@acm .org> wrote in message
news:3F******** *******@acm.org ...

hedylogus wrote:

every now and
then rand() produces duplicate random numbers

Of course it does. If it didn't, the numbers wouldn't be random.

Repeat values are a consequence of finite numbers of bits computed by the
algorithm, not randomness itself. Of course with certain lousy
implementations of rand() only a miserly 15 bits (the absolute minimum
allowed by the standard) are provided, resulting in repetition in very short
run lengths.

That's silly. If the numbers were truly random, the expected number of
draws before a duplicate would be much less than the number of possible
results.

How do I avoid this???

std::random_s huffle.

Or get a decent random number generator (31 bits or more). They are readily
available. You will still get repeats if you let your program run for the
rest of your life.

If only 52 draws are made, what difference does drawing from 2^32 values
rather than 2&16 make? The chance of some number occurring twice in
those 52 draws would presumably still be significantly greater than
zero in the latter case.

(To the OP:)
Search for Fisher-Yates shuffle for the usual (optimal) implementation
of random_shuffle.

Regards,
Buster

[Buster Copley]

Buster Copley wrote:

If only 52 draws are made, what difference does drawing from 2^32 values
rather than 2&16 make? The chance of some number occurring twice in
those 52 draws would presumably still be significantly greater than
zero in the latter case.
That is, 2^16, and I hope you can guess which case I meant.
Regards,
Buster

[Pete Becker]

Cy Edmunds wrote:

"Pete Becker" <pe********@acm .org> wrote in message
news:3F******** *******@acm.org ...

hedylogus wrote:

every now and
then rand() produces duplicate random numbers
Of course it does. If it didn't, the numbers wouldn't be random.

Repeat values are a consequence of finite numbers of bits computed by the
algorithm, not randomness itself.

No. Suppose you roll a six-sided die five times and you get 5, 2, 3, 6,
and 1. Do you expect 4 to come up next?

Of course with certain lousy implementations of rand() only a miserly 15 bits (the absolute minimum
allowed by the standard) are provided, resulting in repetition in very short
run lengths.

How do I avoid this???

std::random_shu ffle.

Or get a decent random number generator (31 bits or more).

Won't help, if your technique is wrong. That's why random_shuffle isn't
called rand. They do different things.

--

"To delight in war is a merit in the soldier,
a dangerous quality in the captain, and a
positive crime in the statesman."
George Santayana

"Bring them on."
George W. Bush

[Danny Anderson]

"hedylogus" <xx**********@y ahoo.xxx> wrote in message
news:<%JhUa.147 299$H17.51207@s ccrnsc02>

....but every now and
then rand() produces duplicate random numbers causing me to "lose" a card.
How do I avoid this??? I've attached my code below for reference. Thanks
in advance.

Despite quite a few answers already, I will take a stab at this in a
'newbie' context, since I am barely, if at all, past that stage myself.
rand() produces a stream of psuedo-random numbers based on a seed, the
computer clock in your case.
rand() cannot ensure that there are no duplicates in that stream. I can
think of three options for you in this case:

1) Find a more sophisticated random number generator. This is reasonable,
but IMHO, you would be better off with #2 or #3

2) Develop a test condition so you can "draw again" if the random number
tries to draw more than once from the same spot in CardDeck[]. This is a
reasonable solution, except for the fact that your code show s that you
have at least a passing familiarity with STL.

3) Go for the double bonus: go for random_shuffle like Rolf suggested. Not
only will you solve your duplication problem, your code will be much smaller
and cleaner. The bonus-bonus is that your code will be very readable, a
definite plus as far as grading goes.

[Pete Becker]

Danny Anderson wrote:

1) Find a more sophisticated random number generator. This is reasonable,
but IMHO, you would be better off with #2 or #3
This is not the problem.

2) Develop a test condition so you can "draw again" if the random number
tries to draw more than once from the same spot in CardDeck[]. This is a
reasonable solution, except for the fact that your code show s that you
have at least a passing familiarity with STL.
This becomes slower as you use up numbers. Bad approach.

3) Go for the double bonus: go for random_shuffle like Rolf suggested. Not
only will you solve your duplication problem, your code will be much smaller
and cleaner. The bonus-bonus is that your code will be very readable, a
definite plus as far as grading goes.

Or learn how to do it yourself. It's not that hard, and provides some
useful insights.

--

"To delight in war is a merit in the soldier,
a dangerous quality in the captain, and a
positive crime in the statesman."
George Santayana

"Bring them on."
George W. Bush

[Danny Anderson]

> > 3) Go for the double bonus: go for random_shuffle like Rolf suggested.
Not

only will you solve your duplication problem, your code will be much smaller and cleaner. The bonus-bonus is that your code will be very readable, a
definite plus as far as grading goes.

Or learn how to do it yourself. It's not that hard, and provides some
useful insights.

Maybe so- my take was that the guy was using STL structures and some general
algorithms like sort(), but didn't seem to know about random_shuffle. In
that case, I think random_shuffle is a really good choice. I understand the
DIY rationalization , but it seems to me a lot of stuff works in the opposite
order: learn to use the tools available first, the improve and fabricate new
better tools when the need arises.

Just an opinion, don't flog me for it too much. :)

Danny

[Cy Edmunds]

"Pete Becker" <pe********@acm .org> wrote in message
news:3F******** *******@acm.org ...

Cy Edmunds wrote:

"Pete Becker" <pe********@acm .org> wrote in message
news:3F******** *******@acm.org ...

hedylogus wrote:
>
> every now and
> then rand() produces duplicate random numbers

Of course it does. If it didn't, the numbers wouldn't be random.

Repeat values are a consequence of finite numbers of bits computed by the algorithm, not randomness itself.

No. Suppose you roll a six-sided die five times and you get 5, 2, 3, 6,
and 1. Do you expect 4 to come up next?

No, I don't. But if I did get a 4, on the seventh roll I would certainly get
a duplicate. This has nothing to do with randomness. It only has to do with
the fact that a die only has six sides. Hence:

"Repeat values are a consequence of finite numbers of bits computed by the
algorithm, not randomness itself."

<snip>

--
Cy
http://home.rochester.rr.com/cyhome/