random_shuffle()
Graham Cox
using different seed numbers, the output is identical? Is there a way
to get random_shuffle() (or any similar function) to shuffle the
vector differently using different seeds on different runs of the
program? - Any help would be much appreciated - thanks
Simplified program:
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
int x;
cin >> x;
std::srand(x);
vector<int> vec;
for(int i=0; i<5; i++)
{
vec.push_back(i);
}
random_shuffle(vec.begin(),vec.end());
for(int i=0; i<5; i++)
{
cout << vec[i] << endl;
}
}
tom_usenet
>Does anyone know why on subseqent runs of the following short program,
>using different seed numbers, the output is identical? Is there a way
>to get random_shuffle() (or any similar function) to shuffle the
>vector differently using different seeds on different runs of the
>program? - Any help would be much appreciated - thanks
There is no standard way to seed the random number generator used by
random_shuffle. Some libraries let you use srand (which is a
non-conforming extension, I believe), and some others offer an
alternative extension function to do the seeding (consult your docs).
However, the safe way is as follows:
>
>Simplified program:
>
>#include <iostream>
>#include <vector>
>#include <algorithm>
#include <cstdlib>
struct Rand
{
int operator()(int i) const
{
return (int)(((double)std::rand() * i) / (RAND_MAX +
1.0));
}
};
>using namespace std;
>
>int main()
>{
> int x;
> cin >> x;
> std::srand(x);
>
> vector<int> vec;
>
> for(int i=0; i<5; i++)
> {
> vec.push_back(i);
> }
>
Rand myrand;
random_shuffle(vec.begin(),vec.end(), myrand);
>
> for(int i=0; i<5; i++)
> {
> cout << vec[i] << endl;
> }
>}
Tom
Graham Cox
P.J. Plauger
news:3ed4bea6....@news.easynet.co.uk...
> There is no standard way to seed the random number generator used by
> random_shuffle. Some libraries let you use srand (which is a
> non-conforming extension, I believe), and some others offer an
> alternative extension function to do the seeding (consult your docs).
Why do you believe that random_shuffle may not use rand?
P.J. Plauger
Dinkumware, Ltd.
http://www.dinkumware.com
tom_usenet
<p...@dinkumware.com> wrote:
>"tom_usenet" <tom_u...@hotmail.com> wrote in message
>news:3ed4bea6....@news.easynet.co.uk...
>
>> There is no standard way to seed the random number generator used by
>> random_shuffle. Some libraries let you use srand (which is a
>> non-conforming extension, I believe), and some others offer an
>> alternative extension function to do the seeding (consult your docs).
>
>Why do you believe that random_shuffle may not use rand?
Well, the C standard says (a C99 draft actually):
7.20.2.1 The rand function
[...]
3 The implementation shall behave as if no library function calls the
rand function.
You're far better placed than me to say whether text of that sort in
the C standard is normative for the C++ standard, and whether
"library" above includes the C++ standard...
I'd expect the following to work:
#include <cstdlib>
#include <cassert>
#include <algorithm>
using namespace std;
int main()
{
int array[3] = {1, 2, 3};
srand(10);
int num1 = rand();
srand(10);
random_shuffle(array, array + 3);
int num2 = rand();
assert(num1 == num2);
}
However, it asserts on all the compilers I have ready access to (gcc
2.95, gcc 3.2, como 4.3, vc6).
I think random_shuffle should call rand, but I think the standard
should be changed to enforce it...
Tom
Graham Cox
random_shuffle(vec.begin(), vec.end(), rand);
or some variation - as I can't get that to compile
Howard Hinnant
<tom_u...@hotmail.com> wrote:
I agree 100% with your analysis, and with your conclusion. You can
also add Metrowerks to your list of vendors that use rand in
random_shuffle (because that's what most of our customers expect).
--
Howard Hinnant
Metrowerks
John Ericson
"Graham Cox" <ga...@tc.bham.ac.uk> wrote in message
news:3ED4E100...@tc.bham.ac.uk...
> Do you mean:
>
> random_shuffle(vec.begin(), vec.end(), rand);
>
> or some variation - as I can't get that to compile
The third parameter of random_shuffle takes an integral
value of type 'difference_type', so you can't just use rand
directly!
Best Regards, John E.
Shane Beasley
<3ed4d279....@news.easynet.co.uk> on Wednesday, May 28, 2003
11:00 AM:
> >> There is no standard way to seed the random number generator used
by
> >> random_shuffle. Some libraries let you use srand (which is a
> >> non-conforming extension, I believe), and some others offer an
> >> alternative extension function to do the seeding (consult your
docs).
>
> >Why do you believe that random_shuffle may not use rand?
25.2.11 doesn't say that it does. It doesn't say that it doesn't,
either, but that doesn't mean that it does.
It *does* refer to "a particular random number generating function
object /rand/", but that's not std::rand; that's the name they gave to
the third parameter of the trinary overload of std::random_shuffle.
> Well, the C standard says (a C99 draft actually):
C99 is not normative to C++, only C89; and (IIRC) any rules in C89
involving library function/header intermingling do not apply to C++.
> I think random_shuffle should call rand, but I think the standard
> should be changed to enforce it...
I wouldn't argue there. The only formal PRNG in C++ is std::rand; it
doesn't help portability if, for no apparent reason, the Standard allows
implementations to make up their own PRNG just for std::random_shuffle,
and to force users to write implementation-dependent code if they want
to alter the behavior of that PRNG (if the implementation allows this at
all).
- Shane
Jerry Coffin
p...@dinkumware.com says...
[ ... ]
> Why do you believe that random_shuffle may not use rand?
According to $26.5, the rand() in the C++ standard library is the same
as the rand in the C standard library from its normative reference (i.e.
C90 and 95). According to $7.10.2.1 in the C90 standard, "The rand
function shall behave as if no library function calls the rand
function." I doubt this provision was changed in C95 (it's present in
C99 as 7.20.2.1/3).
As such, it appears to me that if random_shuffle uses rand, it has to do
so in a way that this usage is transparent to the user, such as by
allocating separate storage for the current seed value used by
random_shuffle and by direct use of rand().
For one example, defining rand as something like:
int rand(_State_t *s=NULL);
seems to fulfill all requirements -- it can still be called in the
normal fashion without an argument, in which case it would use some
default storage for the state. OTOH, when random_shuffle used rand(),
it would pass a state variable, so it could maintain a separate sequence
from that used by direct calls to rand().
At least IIRC, the standard explicitly allows extra parameters like this
as long as defaults are provided for the extra parameters so they can be
called in the usual fashion.
OTOH, this still doesn't really address the original question -- with
this sort of setup, you'd presumably define srand something like:
void srand(unsigned, _State_t *init=NULL);
and (again) if you passed a _State *, it would initialize that state,
but if none was passed, it would initialize the default state. Thus, a
normal call to srand would have no effect on the sequence used by
random_shuffle.
In the end, random_shuffle either does or does not use the normal state
used by direct calls to rand(). If there is only one state, using
random_shuffle violates the requirements on rand(). If there are two
separate states, then initializing the default state with a normal call
to srand should have no effect on the second state.
I suppose you could have a default call to srand initialize _both_
states, and then have rand() modify one, and random_shuffle modify the
other, but this means the two would use the same sequence in parallel,
which would generally be undesirable.
--
Later,
Jerry.
The universe is a figment of its own imagination.