random data in structure - checking for no double values

[Erich Pul]

hi!

i got a structure, which should be filled with random integer values
(it is in fact a generator for numbers like in a lotto), but these
values must not be recurring, so no double occurrences are desired.

my code:

<code>
Tipp* ziehung() // Tipp* is the function
{
Node *bewK; // a node that is my index
Tipp ziehungT; // a new struct for storing the random values
int x;

x = 0;
srand(time(NULL)); // init for the rand()
while(x<=20) // for testing, gimme 20 values
{
ziehungT.z1 = (rand() % 45) +1; // data input in the
struct's members
ziehungT.z2 = (rand() % 45) +1;
ziehungT.z3 = (rand() % 45) +1;
ziehungT.z4 = (rand() % 45) +1;
ziehungT.z5 = (rand() % 45) +1;
ziehungT.z6 = (rand() % 45) +1;

printf("\nGezogen wurden folgende Zahlen: %d %d %d %d %d %d",
ziehungT.z1,ziehungT.z2,ziehungT.z3,ziehungT.z4,ziehungT.z5,ziehungT.z6);
x++;
}
}

</code>

is there a possibility to circumvent packing an array with the values
and running through several loops?

TIA,

 

[Richard Bos]

i got a structure, which should be filled with random integer values
(it is in fact a generator for numbers like in a lotto), but these
values must not be recurring, so no double occurrences are desired.

my code:

<code>
Tipp* ziehung() // Tipp* is the function

No, ziehung() is the function. Tipp * is the type of its return value.

ziehungT.z1 = (rand() % 45) +1; // data input in the
struct's members
ziehungT.z2 = (rand() % 45) +1;
ziehungT.z3 = (rand() % 45) +1;
ziehungT.z4 = (rand() % 45) +1;
ziehungT.z5 = (rand() % 45) +1;
ziehungT.z6 = (rand() % 45) +1;

So that won't work, then.

is there a possibility to circumvent packing an array with the values
and running through several loops?

No. Is there any problem with filling an array of 45 elements with 1-45,
shuffling it (takes only a single loop of at most 44 iterations - in
this case you need only 6) and then taking the first 6 elements of the
shuffled array?

Richard

 

[Erich Pul]

Tipp* ziehung() // Tipp* is the function

No, ziehung() is the function. Tipp * is the type of its return value.

yep, i meant that ; )

[...]

So that won't work, then.

nah, that works perfectly - the problem is that there *MAY* be values
that occur twice or more (sometimes they do, sometimes not)

No. Is there any problem with filling an array of 45 elements with 1-45,
shuffling it (takes only a single loop of at most 44 iterations - in
this case you need only 6) and then taking the first 6 elements of the
shuffled array?

basically not, but that is just a variation of the same problem,
because there is no proof that there won't be values that occur twice.

greetings,

 

[Vladimir Oka]

Erich Pul wrote:

Don't snip attributions (who said what). This was by Richard Bos:

basically not, but that is just a variation of the same problem,
because there is no proof that there won't be values that occur twice.

I don't think you read Richard's suggestion carefully. It is guaranteed
to give all different numbers. E.g.:

0 1 2 3 4 5 6 7 8 9

<shuffle>

1 7 3 5 6 2 4 9 8 0

<take first N>

Probably the easiest way to shuffle is to swap N pairs of randomly
chosen elements.

 

[Erich Pul]

Vladimir Oka schrieb:

I don't think you read Richard's suggestion carefully. It is guaranteed
to give all different numbers. E.g.:

0 1 2 3 4 5 6 7 8 9

<shuffle>

1 7 3 5 6 2 4 9 8 0

<take first N>

Probably the easiest way to shuffle is to swap N pairs of randomly
chosen elements.

well, you are right - sorry - must use two eyes from now on. thanks,
i'll try that.

E

 

[Duncan Muirhead]

hi!

i got a structure, which should be filled with random integer values
(it is in fact a generator for numbers like in a lotto), but these
values must not be recurring, so no double occurrences are desired.

my code:

<code>
Tipp* ziehung() // Tipp* is the function
{
Node *bewK; // a node that is my index
Tipp ziehungT; // a new struct for storing the random values
int x;

x = 0;
srand(time(NULL)); // init for the rand()
while(x<=20) // for testing, gimme 20 values
{
ziehungT.z1 = (rand() % 45) +1; // data input in the
struct's members
ziehungT.z2 = (rand() % 45) +1;
ziehungT.z3 = (rand() % 45) +1;
ziehungT.z4 = (rand() % 45) +1;
ziehungT.z5 = (rand() % 45) +1;
ziehungT.z6 = (rand() % 45) +1;

printf("\nGezogen wurden folgende Zahlen: %d %d %d %d %d %d",
ziehungT.z1,ziehungT.z2,ziehungT.z3,ziehungT.z4,ziehungT.z5,ziehungT.z6);
x++;
}
}

</code>

is there a possibility to circumvent packing an array with the values
and running through several loops?

TIA,

I think this is off topic for this news group. However I'd suggest
creating an array holding 1..45, shuffling it (search for Knuth
Shuffling algorithm) and then taking the last 6 entries from the array.
For example:
void KnuthShuffle(int n, int* deck)
{ int r;
while( --n>0)
{ /* r = "random" number between 0 and n inclusive */
/* swap deck[n] and deck[r] */
}
}
If speed is very important, then you could just go round the loop 6 times,
because the last 6 entries won't change after that.

By the way, generating a random integer between 1 and 45 is better (if
somewhat more slowly) done by
1 + 45*((double)rand()/(RAND_MAX+1.0)) than by rand() % 45) +1.
The latter will be more sensitive to the low bits being highly
correlated between calls to rand().
Duncan

 

[Erich Pul]

I think this is off topic for this news group. However I'd suggest

uhm.. why?

creating an array holding 1..45, shuffling it (search for Knuth
Shuffling algorithm) and then taking the last 6 entries from the array.
For example:
void KnuthShuffle(int n, int* deck)
{ int r;
while( --n>0)
{ /* r = "random" number between 0 and n inclusive */
/* swap deck[n] and deck[r] */
}
}
If speed is very important, then you could just go round the loop 6 times,
because the last 6 entries won't change after that.

By the way, generating a random integer between 1 and 45 is better (if
somewhat more slowly) done by
1 + 45*((double)rand()/(RAND_MAX+1.0)) than by rand() % 45) +1.
The latter will be more sensitive to the low bits being highly
correlated between calls to rand().
Duncan

thank you, i will focus on that for my program

E

 

[Vladimir Oka]

uhm.. why?

Because c.l.c deals in Standard C language issues only, not general
algorithm questions (that's what comp.programming is for). If the
question tingles the imagination sufficiently, or is easily dealt with
you can expect to get answers, though (but don't try to abuse this).

 

[Richard Heathfield]

Vladimir Oka said:

Probably the easiest way to shuffle is to swap N pairs of randomly
chosen elements.

I chose N = 6, and ran 1,000,000 trials. Using your method, I got a standard
deviation of 9.63, whereas by swapping N pairs of elements chosen randomly
between i and N, where i was the loop control, I got a standard deviation
of 9.15.

for(i = 0; i < N; i++)
{
r = i * (rand() / (RAND_MAX + 1.0));
if(i != r)
{
swap(d + i, d + r);
}
}

 

[Erich Pul]

Because c.l.c deals in Standard C language issues only, not general
algorithm questions (that's what comp.programming is for). If the
question tingles the imagination sufficiently, or is easily dealt with
you can expect to get answers, though (but don't try to abuse this).

ok, maybe i should have mentioned that i'm currently learning C, so if
i make a post here, expect the volume of my question to be quite...
unpredictable... : )

but thx anyway for the replies

E

 

[Vladimir Oka]

Vladimir Oka said:


I chose N = 6, and ran 1,000,000 trials. Using your method, I got a standard
deviation of 9.63, whereas by swapping N pairs of elements chosen randomly
between i and N, where i was the loop control, I got a standard deviation
of 9.15.

I said "easiest" not "best".

(I also did not mean "N" to be the number of random numbers the OP
wanted.)

 

[Richard Bos]

Erich Pul wrote:

Don't snip attributions (who said what). This was by Richard Bos:


I don't think you read Richard's suggestion carefully. It is guaranteed
to give all different numbers. E.g.:

0 1 2 3 4 5 6 7 8 9

<shuffle>

1 7 3 5 6 2 4 9 8 0

<take first N>

Probably the easiest way to shuffle is to swap N pairs of randomly
chosen elements.

No, that's not the easiest way to shuffle; that's no way to shuffle at
all. Especially if your large N is 45 and your small n is only 6. The
chance of the n shuffles involving only the last N-n elements is pretty
large. It _is_ possible to use this method, but your number of swaps
must be much larger than n, and probably larger than N. And it mustn't
be too large, either, or it turns out inefficient. You need to find the
sweet spot between badly shuffled - or even hardly shuffled at all - and
spending too much time on it, and that sweet spot is very much not easy
to find.
The easy way to shuffle is what amounts to an inverse selection sort:
take the sorted array, then for each member, select a random member from
the unshuffled part of the array (including, vitally, the current
member, otherwise you'll never get shuffles like 45321 or 25143) and
swap the current member with that random member.
If your members are all contiguous, ascending numbers, there's a trick
to make it somewhat more efficient, but slightly less easy to read,
which I'll leave as an exercise to the reader.

Richard

 

[CBFalconer]

Vladimir Oka said:


I chose N = 6, and ran 1,000,000 trials. Using your method, I got a standard
deviation of 9.63, whereas by swapping N pairs of elements chosen randomly
between i and N, where i was the loop control, I got a standard deviation
of 9.15.

for(i = 0; i < N; i++)
{
r = i * (rand() / (RAND_MAX + 1.0));
if(i != r)
{
swap(d + i, d + r);
}
}

Did you consider whether or not rand() is capable of generating 0?

 

[Erich Pul]

to come back to the original topic:

it may be a bit crude, but i think i have found a solution to my
problem that i need reviewal of:

i use an array of 6 numbers which are generated using the original
rand(). then i put this array into a function that uses some sort of
bubble-sort logic (2 loops) to check wether a[x] == a[y] (x and y being
the loop vars).

if an occurrence is found, an if-statement selects wether the a[y]
value is <= 44 (as 45 being the hightest value allowed in my program).
if that is so, a value of 1 is added up to a[y], so no double values
anymore.

i hope i made the technique clear, i know it is far from perfect and i
would not employ it in a real program but since my deadline is tomorrow
and this program is meant as an example app i think that can be
tolerated.

thanks!

E

 

[Vladimir Oka]

No, that's not the easiest way to shuffle; that's no way to shuffle at
all. Especially if your large N is 45 and your small n is only 6. The
chance of the n shuffles involving only the last N-n elements is pretty
large. It _is_ possible to use this method, but your number of swaps
must be much larger than n, and probably larger than N. And it mustn't
be too large, either, or it turns out inefficient. You need to find the
sweet spot between badly shuffled - or even hardly shuffled at all - and
spending too much time on it, and that sweet spot is very much not easy
to find.

So it /is/ a way to shuffle after all? One just has to tune it
properly.

I never said anything about quality of my proposed shuffling method. It
was hardly a proper proposal at all. I'm not an expert in this area. It
was all off-topic anyway. OP was advised where to look for the on-topic
replies as well.

I give up now.

 

[Pofy]

No. Is there any problem with filling an array of 45 elements with 1-45,
shuffling it (takes only a single loop of at most 44 iterations - in
this case you need only 6) and then taking the first 6 elements of the
shuffled array?

Instead of shuffling, which requires many loops for good randomness,
would it not be better to simply pick one of the 45 elements at random.
Then, if it was not the last element, swap in the element in position
45 with the one you just picked. Now repeat but pick form the first 44
elements and so on until you have the desired number of random values.

 

[Chris Dollin]

Instead of shuffling, which requires many loops for good randomness,

Just the one.

would it not be better to simply pick one of the 45 elements at random.
Then, if it was not the last element, swap in the element in position
45 with the one you just picked. Now repeat but pick form the first 44
elements and so on until you have the desired number of random values.

And there you pretty much have the shuffling loop.

["shuffle" doesn't need to mean "a simulation of a human's rubbish
attempt at randomising card order".]

 

[Richard Heathfield]

CBFalconer said:

Did you consider whether or not rand() is capable of generating 0?

Let's assume it isn't, and see where it takes us. We will assume RAND_MAX is
32767, that the numbers 1-32767 are returned with a reasonable
distribution, and that N = 6. Let us now write a little program to test all
possible pseudo-random values:

#include <stdio.h>

#define MAX 32767
#define N 6

int main(void)
{
unsigned long count[N] = {0};
int i;
int r;

for(i = 1; i < 32767; i++)
{
r = N * (i / (MAX + 1.0));
++count[r];
}
for(i = 0; i < N; i++)
{
printf("%d: %lu\n", i, count);
}
return 0;
}
Here are the results:

0: 5461
1: 5461
2: 5461
3: 5462
4: 5461
5: 5460

And here are the results if we count from 0:

0: 5462
1: 5461
2: 5461
3: 5462
4: 5461
5: 5460

Not a huge amount of difference, is there?

I re-ran the tests I did earlier, but with the slight change that, if rand()
returned 0, I threw it away and got the next value. The results are:

Vladimir's technique: Standard Dev of 9.63
The canonical technique: Standard Dev of 9.15

 

[Pofy]

Just the one.

True, I was stuck in the thought of the "swap N pairs of randomly
chosen elements" of another post.

 

[Richard Tobin]

Instead of shuffling, which requires many loops for good randomness,
would it not be better to simply pick one of the 45 elements at random.
Then, if it was not the last element, swap in the element in position
45 with the one you just picked. Now repeat but pick form the first 44
elements and so on until you have the desired number of random values.

That's what people usually mean by shuffling in this context.

-- Richard