By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
446,305 Members | 1,614 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 446,305 IT Pros & Developers. It's quick & easy.

random data in structure - checking for no double values

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

Jun 22 '06 #1
Share this Question
Share on Google+
19 Replies


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 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
Jun 22 '06 #2

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 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,
--
Erich Pul

Jun 22 '06 #3

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 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.


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.

Jun 22 '06 #4

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

Jun 22 '06 #5

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

Jun 22 '06 #6

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

Jun 22 '06 #7

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).

Jun 22 '06 #8

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)
Jun 22 '06 #9

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

Jun 22 '06 #10

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.)

Jun 22 '06 #11

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 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.


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
Jun 22 '06 #12

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
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

Jun 22 '06 #13

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 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.


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.


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.

Jun 22 '06 #14

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, 2002-03-13
"No, we've had no evidence that Saddam Hussein was involved
with September the 11th." - George Walker Bush 2003-09-17
Jun 22 '06 #15

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 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.

Jun 22 '06 #16

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 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,


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
"No-one here is exactly what he appears." G'kar, /Babylon 5/

Jun 22 '06 #17

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 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[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 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
--
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)
Jun 22 '06 #18

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 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,


Just the one.


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

Jun 22 '06 #19

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

Jun 22 '06 #20

This discussion thread is closed

Replies have been disabled for this discussion.