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

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

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.

Quote:

---

Originally Posted by tabstop

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

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.

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

---

Quote:

---

Originally Posted by King Mir

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.

Quote:

---

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.

Quote:

---

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

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.

Quote:

---

Originally Posted by esbo

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.

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() % MAX) )] ==0)
    array[gnum]=gnum,count++;
  if(count==n)/// where n is required number of elements
  break;
 }

---

//Hence you got n different numbers

cheers :)

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

---

Quote:

---

Originally Posted by King Mir

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.

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()%(i +1)] );

---

See, the code's shorter even.

Very nice, King Mir!

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

---