How can I asign a random values to an array without repeating the value. Please help.

This is a discussion on How can I asign a random values to an array without repeating the value. Please help. within the C Programming forums, part of the General Programming Boards category; Dear Cprogramming members, Hello and good day to everyone. I just want to ask how would I assign a value ...

  1. #1
    Registered User MarkSquall's Avatar
    Join Date
    Aug 2007
    Posts
    27

    Post How can I asign a random values to an array without repeating the value? Please help.

    Dear Cprogramming members,


    Hello and good day to everyone. I just want to ask how would I assign a value from 0 to 8 only in an array without repeating its value? I have currently type this code in my program:

    Code:
    int x, num[9];
    .
    .
    .
    for (x=0; x<=8; x++)
    {
        num[x] = rand() % 9;
    }

    But as I watched the value of variables, it seem that there are numbers between 0 to 8 that has been repeated twice, thrice, etc. Is there a way that I could assigned a random but nonrepeating values in an array? Example, if in the first run, the value 4 was assigned in num[0], then value 4 will not be then again assigned to any of the remaining empty array, only 0,1,2,3,5,6,7,8 is only allowed. And I noticed that everytime I run the program, num[0] is always 4, is there a way I could change it?


    Thank you and more power.


    Respectfully yours,

    MarkSquall
    Last edited by MarkSquall; 01-17-2008 at 11:12 PM. Reason: Wrong grammar.

  2. #2
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    The easiest way is probably to keep an auxiliary array such as used[9], originally initialized to all zeros, and is set to 1 when you draw that number. Then you can keep generating numbers until used[x] is 0. (There's probably a method that involves drawing a number between 1 and 9! and generating a permutation, but I don't think that would be "easiest", and it certainly wouldn't scale.)

    As to why num[0] is always 4, that depends on how you seed the RNG. (That is to say, if you don't seed it, you should expect to always get the same run of numbers.)

  3. #3
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    22,312
    It looks like you want an array of 9 integers, each being a distinct integer in the range [0,8].

    In C++, I would populate the array with the integers 0 to 8, then perform a random shuffle. Unfortunately, I have been told that a good random shuffle algorithm is not that trivial to come up with (i.e., it is easy to get it wrong, if you want good random properties), and the C standard library does not have it implemented (though the C++ standard library does have one).

    The auxiliary array idea should also work, but is probably slower as it has to redraw whenever a duplicate is found, and that is bound to occur frequently as the array gets filled.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  4. #4
    Registered User
    Join Date
    Apr 2006
    Posts
    2,053
    Quote Originally Posted by tabstop View Post
    The easiest way is probably to keep an auxiliary array such as used[9], originally initialized to all zeros, and is set to 1 when you draw that number. Then you can keep generating numbers until used[x] is 0. (There's probably a method that involves drawing a number between 1 and 9! and generating a permutation, but I don't think that would be "easiest", and it certainly wouldn't scale.)
    Don't do this. It's a horrible
    algorithm. I complexity is just horrible.

    The best way is to create a sorted list of possible values, and then shuffle it. Shuffleing algorithms can be found on Google.

    Quote Originally Posted by laserlight View Post
    I have been told that a good random shuffle algorithm is not that trivial to come up with (i.e., it is easy to get it wrong, if you want good random properties), and the C standard library does not have it implemented (though the C++ standard library does have one).
    Really? Seems pretty strait forward to me. I guess you can't go wrong with Java's algorithm.
    Last edited by King Mir; 01-17-2008 at 11:28 PM.
    It is too clear and so it is hard to see.
    A dunce once searched for fire with a lighted lantern.
    Had he known what fire was,
    He could have cooked his rice much sooner.

  5. #5
    Fountain of knowledge.
    Join Date
    May 2006
    Posts
    794
    I think you need to use srand and seed it with the curent time or something like that.
    Here is something similar I found.

    Code:
    
    /*********************************************************************
     *
     * Purpose: Demonstrate the 'srand' and 'rand' functions
     * Author:  M.J. Leslie.
     * Date:    11=Nov-94
     *
     *********************************************************************/
    
    #include <time.h>
    #include <stdlib.h>
    
    main()
    {
      int rolls=4;
    					/* This looks DISCUSTING!
    					 * time returns a different value 
    					 * on every execution. And so 
    					 * changes the value passed to 
    					 * srand. See CAST
    					 * for an explanation of 
    					 * (unsigned int) and (time_t)	*/
      srand((unsigned int)time((time_t *)NULL));
    
    					/* Roll the dice.		*/
      while(rolls--)
      {
        printf("Dice value is %d\n", (rand()%6)+1);
      }
    }

  6. #6
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    Quote Originally Posted by King Mir View Post
    Don't do this. It's a horrible
    algorithm. I complexity is just horrible.
    After re-reading, I agree. I hadn't quite grasped that you were always using all the numbers, which means waiting for the RNG to give you the last number you need is a fool's game. Shuffle.

  7. #7
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    22,312
    Really? Seems pretty strait forward to me. I guess you can't go wrong with Java's algorithm.
    Well, "trivial" is relative. It is trivial if you are in the know, but if you are not, then having to come up with a good algorithm and prove that its properties are suitable may not be so trivial. As I recall from an article, programmers have screwed this up when programming gambling games, even though such algorithms have been published (by Knuth?) years earlier.

    I think you need to use srand and seed it with the curent time or something like that.
    Yes, though for the "something like that", I suggest reading Prelude's article on Using rand().
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  8. #8
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    So, you seed the random generator only once, before the first call to random(), and then every sequence of random numbers will be different. BTW that is a feature of random(), in place for testing purposes.

    Tabstops auxiliary array is a good idea for a small number of random numbers being unique. I use that for one of my games. Yes, it has terrible complexity, but even on a P3@1GHz, you wouldn't notice the slow down. You definitely don't want to use this with a larger number (say 500 or more) random numbers. Then you'd be in trouble!

    This is just off-the-cuff, and untested, to give you an idea of what using tabstop's idea is like, in code. You may need to make corrections.

    Code:
    #include <stdio.h>
    #include <time.h>
    
    int unique = 0;
    int trial;
    
    int aux[9] = { 0 };  /* not 8, but 9 - we need 1 - 8, not 0 - 7. Zero element isn't used.*/
    srand((unsigned int)time((time_t *)NULL));
    
    while(unique < 9)  {
       trial = (rand() % 8) + 1;
       if(aux[trial])     /* or if(aux[trial] == 1 */
           continue;    /* start the while loop again at the top, it's a duplicated number */
       
       unique++;      /* not a duplicated number if it reaches here, so increment unique */
       aux[trial] = 1; /* and set the aux[trial] number to 1. That number has been used, now */
    }

    The shuffle is very nice indeed for this, but not so easy to code up.

  9. #9
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Posts
    23,033
    Quote Originally Posted by esbo View Post
    I think you need to use srand and seed it with the curent time or something like that.
    Here is something similar I found.
    main explicitly returns int.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  10. #10
    Registered User
    Join Date
    Jan 2008
    Posts
    11
    hi....as you are interested in getting values of range [0,8]...wat i would suggest is maintain an array of that size...
    Code:
    #define MAX 10
    Code:
    int array[MAX];
    now,wat u have to do is some what like this

    Code:
    srand(time(NULL));
    int count=0;
    int gnum=-1;
    for(;;) 
     {
       if( array[ (gnum=(int)(rand() &#37; MAX) )] ==0) 
        array[gnum]=gnum,count++;
      if(count==n)/// where n is required number of elements
       break;
     }
    //Hence you got n different numbers

    cheers

  11. #11
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    >srand((unsigned int)time((time_t *)NULL));
    FYI, because this came up recently. Neither of those casts are necessary, except possibly to silence warnings in the case of casting time.

    1) There's no need to cast NULL to (time_t*) because NULL is a generic null pointer type. It's always implicitly convertible to an object pointer type. That gives you this:
    Code:
    srand ( (unsigned)time ( NULL ) );
    2) There's no need to cast time because time_t is an arithmetic type. It'll be implicitly converted to unsigned int with or without the cast. However, the conversion may not be benign, and compilers may warn about it. You should heed this warning, because if time_t has a type and value that isn't representable as unsigned int, the behavior of this conversion is undefined. Removing the cast gives you this:
    Code:
    srand ( time ( NULL ) );
    Much simpler, but still non-portable. You can still use the current time with a little more work to avoid the overflow issue:
    Code:
    double diff = difftime ( 0, time ( NULL ) );
    double sec = fmod ( diff, UINT_MAX + 1.0 );
    
    srand ( (unsigned)sec );
    But this bounds you to getting a new seed only once per second and the cast is still likely to be needed for a clean compile (loss of precision warnings from double to unsigned int).

    Another option is to hash the time_t in such a way that you don't rely on its representation or have to worry about overflow errors on conversion:
    Code:
    unsigned hash ( void *key, size_t len )
    {
      unsigned char *p = key;
      unsigned h = 0;
      size_t i;
    
      for ( i = 0; i < len; i++ )
        h = 33 * h ^ p[i];
    
      return h;
    }
    
    time_t now = time ( NULL );
    
    srand ( hash ( &now, sizeof now ) );
    My best code is written with the delete key.

  12. #12
    Malum in se abachler's Avatar
    Join Date
    Apr 2007
    Posts
    3,189
    Quote Originally Posted by King Mir View Post
    Don't do this. It's a horrible
    algorithm. I complexity is just horrible.
    I did the factorial thign once, its not hard to do for small data sets. with 21 or fewer members. Above that and you have problems storing teh random permutation in native data sizes.
    Last edited by abachler; 01-18-2008 at 10:43 AM.
    Until you can build a working general purpose reprogrammable computer out of basic components from radio shack, you are not fit to call yourself a programmer in my presence. This is cwhizard, signing off.

  13. #13
    Registered User
    Join Date
    Apr 2006
    Posts
    2,053
    Here's the shuffle algorithm. I'll concede that if you don't know it, you can screw it up. But with the algorithm readily available it's not hard to code.
    Code:
    for(int i = array_size-1 ; i; --i)
        swap( array[i], array[rand()&#37;(i +1)] );
    See, the code's shorter even.
    It is too clear and so it is hard to see.
    A dunce once searched for fire with a lighted lantern.
    Had he known what fire was,
    He could have cooked his rice much sooner.

  14. #14
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    Very nice, King Mir!

  15. #15
    - - - - - - - - oogabooga's Avatar
    Join Date
    Jan 2008
    Posts
    2,808
    Problems with shuffling algorithms are a random number generator issue. For example, in MinGW, rand() returns an int, with a maximum value (RAND_MAX) of 32767.

    Modding a number in that range by 52 (say), causes the lowest few numbers (0 to 8, I think) to have a 1/631 greater chance of being picked, because they are in the RAND_MAX range (mod-wise) one extra time each.

    n = rand() * max / (RAND_MAX+1); is better (n in [0, max-1]), but it really just spreads the favored numbers out so they are not all at the beginning of your range.

    Another problem is that since a deck of cards has 52! permutations while RNGs typically have periods of 2^32 (or even, in the case of rand(), 2^15). I'm not sure exactly how this matters, but the difference in value is huge. Even 2^64 is dwarfed by 52! = 2^225.6 (as shown by a quick calculation):
    Code:
    /* Fact52asPow2.c
     * Calculates lg 52! by summing log base 2 of 2 to 52.
     * The answer given is 225.58.... */
    #include <stdio.h>
    #include <math.h>
    #define log2(n) (log(n)/log(2)) /* log base 2 */
    int main() {
        int i;
        double sum = 0;
        for (i = 2; i <= 52; ++i) sum += log2( i );
        printf( "%f\n", sum );
    }

Page 1 of 2 12 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 2
    Last Post: 11-19-2008, 02:36 PM
  2. question about multidimensional arrays
    By richdb in forum C Programming
    Replies: 22
    Last Post: 02-26-2006, 09:51 AM
  3. Eliminating duplicate values from a 20x2 array
    By desipunjabi in forum C Programming
    Replies: 2
    Last Post: 10-29-2005, 10:11 PM
  4. Another brain block... Random Numbers
    By DanFraser in forum C# Programming
    Replies: 2
    Last Post: 01-23-2005, 05:51 PM
  5. Hi, could someone help me with arrays?
    By goodn in forum C Programming
    Replies: 20
    Last Post: 10-18-2001, 10:48 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21