## digitalmars.D - randomCover not so random?

• dsimcha (31/31) Apr 20 2009 Maybe I'm doing something subtly wrong here, but I've checked all the ob...
• Andrei Alexandrescu (9/28) Apr 20 2009 Here you reseed the random number generator every pass through the outer...
• dsimcha (12/40) Apr 20 2009 Actually, I meant to mention in the original post that I thought of this...
dsimcha <dsimcha yahoo.com> writes:
```Maybe I'm doing something subtly wrong here, but I've checked all the obvious
stuff.

import std.stdio, std.random, std.array;

import dstats.base : Perm;

void main() {
uint[int[]] counts;
immutable int[] foo = [1,2,3];

// Make sure every permutation is represented in counts.
foreach(perm; Perm!int(foo.dup)) {
counts[perm.dup] = 0;
}

foreach(i; 0..10_000) {
int[] result;
foreach(elem; randomCover(foo, Random(unpredictableSeed))) {
result ~= elem;
}
counts[result]++;
}
foreach(k, v; counts) {
writeln(k, "\t", v);
}
}

Output:

2 3 1   0
3 2 1   0
1 3 2   0
3 1 2   0
1 2 3   4929
2 1 3   5071

Note that when I use randomShuffle instead of randomCover, I get a fairly
uniform distribution on the permutation space.
```
Apr 20 2009
Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
```dsimcha wrote:
Maybe I'm doing something subtly wrong here, but I've checked all the obvious
stuff.

import std.stdio, std.random, std.array;

import dstats.base : Perm;

void main() {
uint[int[]] counts;
immutable int[] foo = [1,2,3];

// Make sure every permutation is represented in counts.
foreach(perm; Perm!int(foo.dup)) {
counts[perm.dup] = 0;
}

foreach(i; 0..10_000) {
int[] result;
foreach(elem; randomCover(foo, Random(unpredictableSeed))) {

Here you reseed the random number generator every pass through the outer
loop. Although unpredictableSeed is designed to be unpredictable, it is
_not_ random.

You'd need to have each cover use the same random generator. Here's
where a shortcoming in the design of randomCover becomes evident:
randomCover stores a copy of its generator, which makes it difficult to
support what you need. I will look into a fix.

Andrei
```
Apr 20 2009
dsimcha <dsimcha yahoo.com> writes:
```== Quote from Andrei Alexandrescu (SeeWebsiteForEmail erdani.org)'s article
dsimcha wrote:
Maybe I'm doing something subtly wrong here, but I've checked all the obvious
stuff.

import std.stdio, std.random, std.array;

import dstats.base : Perm;

void main() {
uint[int[]] counts;
immutable int[] foo = [1,2,3];

// Make sure every permutation is represented in counts.
foreach(perm; Perm!int(foo.dup)) {
counts[perm.dup] = 0;
}

foreach(i; 0..10_000) {
int[] result;
foreach(elem; randomCover(foo, Random(unpredictableSeed))) {

Here you reseed the random number generator every pass through the outer
loop. Although unpredictableSeed is designed to be unpredictable, it is
_not_ random.
You'd need to have each cover use the same random generator. Here's
where a shortcoming in the design of randomCover becomes evident:
randomCover stores a copy of its generator, which makes it difficult to
support what you need. I will look into a fix.
Andrei

Actually, I meant to mention in the original post that I thought of this already
and it's not the problem.  When I re-seed the generator every time but use
randomShuffle, I get something pretty uniform looking.

Furthermore, even after I allow a few more clock ticks to go by and re-run the
program, I still get the same thing when using randomCover.  I also tried things
like keeping a Mersenne Twister outside the loop and using successive iterations
of that to seed the generator that I pass to randomCover.

I actually did find the real problem, though.  It's really simple and I've filed
it in Bugzilla.  See http://d.puremagic.com/issues/show_bug.cgi?id=2865 .

Also, since I remember the discussion a while back on how to make randomCover as
efficient as possible, why are we using bool[] instead of BitArray for it?
```
Apr 20 2009