Thread: 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

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.

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.

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.

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

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.

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

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.