P: n/a

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,zi ehungT.z5,ziehungT.z6);
x++;
}
}
</code>
is there a possibility to circumvent packing an array with the values
and running through several loops?
TIA,

EP  
Share this Question
P: n/a

"Erich Pul" <er*******@blackbox.net> wrote: 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 145,
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  
P: n/a

> > Tipp* ziehung() // Tipp* is the function No, ziehung() is the function. Tipp * is the type of its return value.
yep, i meant that ; )
[...] ziehungT.z4 = (rand() % 45) +1; ziehungT.z5 = (rand() % 45) +1; ziehungT.z6 = (rand() % 45) +1;
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 145, 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,

Erich Pul  
P: n/a

Erich Pul wrote:
Don't snip attributions (who said what). This was by Richard Bos: No. Is there any problem with filling an array of 45 elements with 145, 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.
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.  
P: n/a

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  
P: n/a

On Thu, 22 Jun 2006 01:00:45 0700, Erich Pul wrote: 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,zi ehungT.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  
P: n/a

Duncan Muirhead schrieb: 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  
P: n/a

Erich Pul wrote: Duncan Muirhead schrieb:
I think this is off topic for this news group. However I'd suggest
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).  
P: n/a

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);
}
}

Richard Heathfield
"Usenet is a strange place"  dmr 29/7/1999 http://www.cpax.org.uk
email: rjh at above domain (but drop the www, obviously)  
P: n/a

Vladimir Oka schrieb: 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  
P: n/a

Richard Heathfield wrote: 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.
I said "easiest" not "best".
(I also did not mean "N" to be the number of random numbers the OP
wanted.)  
P: n/a

"Vladimir Oka" <no****@btopenworld.com> wrote: Erich Pul wrote:
Don't snip attributions (who said what). This was by Richard Bos:
No. Is there any problem with filling an array of 45 elements with 145, 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.
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 Nn 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  
P: n/a

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
bubblesort logic (2 loops) to check wether a[x] == a[y] (x and y being
the loop vars).
if an occurrence is found, an ifstatement 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  
P: n/a

Richard Bos wrote: "Vladimir Oka" <no****@btopenworld.com> wrote:
Erich Pul wrote:
Don't snip attributions (who said what). This was by Richard Bos:
> No. Is there any problem with filling an array of 45 elements with 145, > 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.
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 Nn 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 offtopic anyway. OP was advised where to look for the ontopic
replies as well.
I give up now.  
P: n/a

Richard Heathfield wrote: 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); } }
Did you consider whether or not rand() is capable of generating 0?

"I don't know where bin Laden is. I have no idea and really
don't care. It's not that important."  G.W. Bush, 20020313
"No, we've had no evidence that Saddam Hussein was involved
with September the 11th."  George Walker Bush 20030917  
P: n/a

Richard Bos wrote: "Erich Pul" <er*******@blackbox.net> wrote: 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 145, 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.  
P: n/a

Pofy wrote: Richard Bos wrote: "Erich Pul" <er*******@blackbox.net> wrote: > 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 145, 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,
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".]

Chris "seeker" Dollin
"Noone here is exactly what he appears." G'kar, /Babylon 5/  
P: n/a

CBFalconer said: Richard Heathfield wrote: 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); } }
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 132767 are returned with a reasonable
distribution, and that N = 6. Let us now write a little program to test all
possible pseudorandom 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[i]);
}
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 reran 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

Richard Heathfield
"Usenet is a strange place"  dmr 29/7/1999 http://www.cpax.org.uk
email: rjh at above domain (but drop the www, obviously)  
P: n/a

Chris Dollin wrote: Pofy wrote:
Richard Bos wrote: "Erich Pul" <er*******@blackbox.net> wrote: > 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 145, 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,
Just the one.
True, I was stuck in the thought of the "swap N pairs of randomly
chosen elements" of another post.  
P: n/a

In article <11**********************@p79g2000cwp.googlegroups .com>,
Pofy <sa*****@hotmail.com> wrote: 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   This discussion thread is closed Replies have been disabled for this discussion.   Question stats  viewed: 3894
 replies: 19
 date asked: Jun 22 '06
