I want to randomly allocate the numbers 1-9 in an arrya of nine elements how do I go about doing it.
I want to randomly allocate the numbers 1-9 in an arrya of nine elements how do I go about doing it.
Then - write the function shuffle_array or search the forumCode:#define MAX_COUNT 9 int array[MAX_COUNT] int index; for(index = 0; index < MAX_COUNT; ++index ) array[index] = index + 1; suffle_array(array, MAX_COUNT);
All problems in computer science can be solved by another level of indirection,
except for the problem of too many layers of indirection.
– David J. Wheeler
An easy way to shuffle an array is to swap random elements several times.
http://cboard.cprogramming.com/searc...earchid=574073 -> http://cboard.cprogramming.com/showthread.php?t=84724
dwk
Seek and ye shall find. quaere et invenies.
"Simplicity does not precede complexity, but follows it." -- Alan Perlis
"Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
"The only real mistake is the one from which we learn nothing." -- John Powell
Other boards: DaniWeb, TPS
Unofficial Wiki FAQ: cpwiki.sf.net
My website: http://dwks.theprogrammingsite.com/
Projects: codeform, xuni, atlantis, nort, etc.
We're not cookingCode:suffle_array(array, MAX_COUNT);
maybe something like this...
...note that i'm not at home, so i can't test this.Code:#include <stdlib.h> #include <time.h> #define ARRAY_SIZE 9 int array[ARRAY_SIZE] = {0}; int i; int r; srand ( (unsigned int)time( NULL ) ); for ( i = 0; i < ARRAY_SIZE; ++i ) { do { r = rand() % ARRAY_SIZE; } while ( array[r] ); array[r] = i + 1; }
Last edited by codepoet; 11-22-2006 at 05:26 PM.
You don't need to cast NULL. [edit] And you should have included <time.h> . . . [/edit]
You're right, that's a better way to do it.
dwk
Seek and ye shall find. quaere et invenies.
"Simplicity does not precede complexity, but follows it." -- Alan Perlis
"Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
"The only real mistake is the one from which we learn nothing." -- John Powell
Other boards: DaniWeb, TPS
Unofficial Wiki FAQ: cpwiki.sf.net
My website: http://dwks.theprogrammingsite.com/
Projects: codeform, xuni, atlantis, nort, etc.
A shuffle_array function is doable in linear time and with constant memory:
1) Start with max_index equal to the size of your array.
2) Choose a random index from 0 to max_index - 1.
3) Swap the chosen index and max_index - 1.
4) Decrement max_index, done if max_index == 0, otherwise repeat to step 2.
The array should already be filled with the values to be shuffled.
anon outlines this general strategy in dwks's second link.
Algorithms like codepoet's could (in worse-case scenario) spend long amounts of time in the do-while part looking for an unselected index, especially with a large array near the end of the shuffle.
Here's my example:
shuffle_array() is the method I described above, shuffle_array2() is codepoet's method.Code:#include <stdio.h> #include <stdlib.h> #include <time.h> #include <sys/timeb.h> #define ARRAY_SIZE 5000 // Shuffles an array in linear ( O(n) ) time. void shuffle_array(int *array, int size) { int max_index, i, temp; for(max_index = size; max_index > 0; --max_index) { // Choose an index. i = rand() % max_index; // Swap items in i and max_index - 1 temp = array[i]; array[i] = array[max_index - 1]; array[max_index - 1] = temp; } } // Shuffles an array... void shuffle_array2(int *array, int size) { int i, r; for ( i = 0; i < size; ++i ) { do { r = rand() % size; } while ( array[r] ); array[r] = i + 1; } } double time_to_double(struct timeb t) { return (double) t.time + (double) t.millitm / 1000.0; } int main() { int x, *array; struct timeb tstart, tend; srand((unsigned int) time(NULL)); array = malloc(sizeof(int) * ARRAY_SIZE); // Fill array with values of 1 to ARRAY_SIZE. for(x = 0; x < ARRAY_SIZE; ++x) { array[x] = x + 1; } // Shuffle: ftime(&tstart); shuffle_array(array, ARRAY_SIZE); ftime(&tend); printf("shuffle_array() ran in %g seconds.\n", time_to_double(tend) - time_to_double(tstart)); // Blank array for(x = 0; x < ARRAY_SIZE; ++x) { array[x] = 0; } // Shuffle: ftime(&tstart); shuffle_array2(array, ARRAY_SIZE); ftime(&tend); printf("shuffle_array2() ran in %g seconds.\n", time_to_double(tend) - time_to_double(tstart)); return 0; }
Finally, you may want to see Prelude's article/notes on using rand() % someinteger and why that might not give entirely random results. Sorry if I abused your code codepoet - shuffle is a pet peeve of mine. See this Wikipedia article (and the section below the linked one) for more info.
EDIT: The array needs to be blanked for shuffle_array2() to work. Silly me. shuffle_array2() fairs much better when used properly. Also: shuffle_array2() will fail with large (>32k element) arrays, at least on my box. RAND_MAX happens to be really small, and it won't ever reach those high indecies. The same bug applies to my implementation, but it will only effect how random the results are. (shuffle_array will return, shuffle_array2 won't.)
EDIT: Of course, for nine items, I'm probably spitting in the wind.
Last edited by Cactus_Hugger; 11-22-2006 at 08:06 PM.
long time; /* know C? */
Unprecedented performance: Nothing ever ran this slow before.
Any sufficiently advanced bug is indistinguishable from a feature.
Real Programmers confuse Halloween and Christmas, because dec 25 == oct 31.
The best way to accelerate an IBM is at 9.8 m/s/s.
recursion (re - cur' - zhun) n. 1. (see recursion)
in that case, here is a solution better suited for higher values of ARRAY_SIZE, as well as being more efficient by limiting the number of calls to rand() to just ARRAY_SIZE...
...note that instead of relying on repeated calls to rand() to chance upon an open index, i now grab a random starting location from it and iterate through one of two loops (ascending or descending, to prevent patterns from appearing) and grab the first open index found along the way.Code:#include <stdlib.h> #include <time.h> #define ARRAY_SIZE 9 int array[ARRAY_SIZE] = {0}; int i; int r; srand ( (unsigned int)time( NULL ) ); for ( i = 0; i < ARRAY_SIZE; ++i ) { r = rand() % ARRAY_SIZE; if ( array[r] ) { int j; if ( r < ARRAY_SIZE / 2 ) { for ( j = r; array[j]; ++j ) { if ( j == ARRAY_SIZE - 1 ) j = -1; } } else { for ( j = r; array[j]; --j ) { if ( j == 0 ) j = ARRAY_SIZE; } } array[j] = i + 1; } else array[r] = i + 1; }
as far as not using modulus with rand(), i'll leave that workaround as an exercise for the original poster. Prelude's article is quite interesting, and is definitely worth a read.
Last edited by codepoet; 11-23-2006 at 02:11 AM.