446,305 Members | 1,614 Online
+ 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: 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++; } } is there a possibility to circumvent packing an array with the values and running through several loops? TIA, -- EP Jun 22 '06 #1
19 Replies

 P: n/a "Erich Pul" 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: 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 1 7 3 5 6 2 4 9 8 0 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 1 7 3 5 6 2 4 9 8 0 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: 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++; } } 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" 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 1 7 3 5 6 2 4 9 8 0 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" 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 1 7 3 5 6 2 4 9 8 0 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" 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" 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 #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" 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 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 position45 with the one you just picked. Now repeat but pick form the first 44elements 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.