Thread: Ramdom numbers in an array

  1. #1
    Registered User
    Join Date
    Sep 2005
    Posts
    92

    Ramdom numbers in an array

    I want to randomly allocate the numbers 1-9 in an arrya of nine elements how do I go about doing it.

  2. #2
    Hurry Slowly vart's Avatar
    Join Date
    Oct 2006
    Location
    Rishon LeZion, Israel
    Posts
    6,788
    Code:
    #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);
    Then - write the function shuffle_array or search the forum
    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

  3. #3
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,057
    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.

  4. #4
    MFC killed my cat! manutd's Avatar
    Join Date
    Sep 2006
    Location
    Boston, Massachusetts
    Posts
    870
    Code:
    suffle_array(array, MAX_COUNT);
    We're not cooking
    Silence is better than unmeaning words.
    - Pythagoras
    My blog

  5. #5
    Logical Aesthetician codepoet's Avatar
    Join Date
    Nov 2006
    Posts
    14
    maybe something like 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;
    }
    ...note that i'm not at home, so i can't test this.
    Last edited by codepoet; 11-22-2006 at 05:26 PM.

  6. #6
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,057
    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.

  7. #7
    int x = *((int *) NULL); Cactus_Hugger's Avatar
    Join Date
    Jul 2003
    Location
    Banks of the River Styx
    Posts
    902
    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:
    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;
    }
    shuffle_array() is the method I described above, shuffle_array2() is codepoet's method.
    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)

  8. #8
    Logical Aesthetician codepoet's Avatar
    Join Date
    Nov 2006
    Posts
    14
    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...

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

    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.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. To Find Largest Consecutive Sum Of Numbers In 1D Array
    By chottachatri in forum C Programming
    Replies: 22
    Last Post: 07-10-2011, 01:43 PM
  2. entering numbers to array in a row whithout length input
    By transgalactic2 in forum C Programming
    Replies: 55
    Last Post: 01-02-2009, 04:02 AM
  3. Merge sort please
    By vasanth in forum C Programming
    Replies: 2
    Last Post: 11-09-2003, 12:09 PM
  4. getting numbers in an array
    By ct26torr in forum C Programming
    Replies: 6
    Last Post: 03-04-2003, 10:31 AM
  5. Help with an Array
    By omalleys in forum C Programming
    Replies: 1
    Last Post: 07-01-2002, 08:31 AM