pls help on how i can generate 4 digit random number that are unique within the set

icylicious · 08-20-2006, 10:43 AM

hi there.. pls help me.. i need to randomly generate a four digit number that are unique within the set. i tried using this:
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int main(void)
{
int i, n=4, seed;

seed = time(NULL);
srand(seed);
for (i=0; i < n; ++i) {
if(i%1 ==0)
putchar('\n');
printf("%7d",rand());
}
printf("\n\n");
return 0;
}

..but the problem is that i cant limit it to a one digit per number genration. please give me an idea what should i do. thanks

perfect_circle · 08-20-2006, 11:50 AM

.but the problem is that i cant limit it to a one digit per number genration. please give me an idea what should i do. thanks

what exactly do you mean by that?
rand%10 will return a 1 digit number
rand%10000 will return an up to 4 digit number

icylicious · 08-21-2006, 01:17 AM

hi thanks for replying on my message.I mean i need to generate four unique numbers. i also tried doing this:
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int main(void)
{
int i, n=4, a, b, c,d;

srand(time(NULL));
for (i=0; i < n; ++i) {

a= rand() % 9 + 0;
b= rand() % 9 + 0;
c= rand() % 9 + 0 ;
d= rand() % 9 + 0;

};
printf("%d%d%d%d\n",a,b,c,d);
return 0;
}
..but the problem again is that sometimes two digits within the set are the same.
thanks.. hoping for your reply

ntubski · 08-21-2006, 10:08 PM

So you want a four digit number where each digit is unique? Just regenerate if a digit is duplicated:

Code:

a = rand() % 10;

do
 b = rand() % 10;
while(b == a);

do
  c = rand() % 10;
while(c == a || c == b);

do
  d = rand() % 10;
while(d == a || d == b || d == c);

note that it's rand() % 10 not rand() % 9 + 0 which would give a number from 0-8

Dark_Helmet · 08-21-2006, 11:56 PM

Looping until getting a unique digit will work, but is unpredictable in the number of times the loop will execute. It might execute once, or repeat forever. If the function is called repeatedly, it could be a significant performance problem. I would suggest something like this instead:

Code:

a = rand() % 10;   /* First digit can be any within the set */
b = rand() % 9;    /* Second digit can be any except one (a) */

/* If a == b, it's safe to add 1 to b, because b's initial value is 0-8 */
if( b == a )
  b++;

c = rand() % 8;    /* Third digit can be any except two (a or b) */

/* If c == a or c == b, add 1 to c until it does not equal a or b.
   c's initial value is 0-7, meaning we can add 1 twice to get
   a unique value without violating the set. */
if( ( c == a ) || ( c == b ) )
{
  c++;
  if( ( c == a ) || ( c == b ) )
    c++;
}

/* More of the same for d. Check against a, b, and c for uniqueness */
d = rand() % 7;    /* Fourth digit can be any except three (a, b, or c) */
if( ( d == a ) || ( d == b ) || ( d == c ) )
{
  d++;
  if( ( d == a ) || ( d == b ) || ( d == c ) )
  {
    d++;
    if( ( d == a ) || ( d == b ) || ( d == c ) )
      d++;
  }
}

That bit of logic has no loops and its worst case occurs when all the if statements are triggered. There may be a more efficient way to code it, but the code above illustrates the idea.

demon_vox · 08-22-2006, 09:34 AM

Hi all,
I liked the chanllenge so I wrote another solution. This solution is more flexible since it can generate (probably not optimal) a unique sequence of N digits choosing from M numbers.
Hope you like it!

Code:

#include <stdio.h>
#include <stdlib.h>

int *makeRandom(int numberDigits, int bagSize);

int main() {
    int *myNumbers;
    int x;
    myNumbers = makeRandom(4, 10); // 4 digit number, choosing from 9 digits options
    for(x = 0; x < 4; x++) {
	printf("%d ", myNumbers[x]);
    }
    printf("\n");
    free(myNumbers);
    return 0;
}


int *makeRandom(int numberDigits, int bagSize) {
    // This is the
    int *bagOfNumbers = (int *) malloc (bagSize * sizeof(int));

    // This will be the resulting array
    int *generatedNumbers = (int *) malloc (numberDigits * sizeof(int));

    
    int counter;
    int randomIndex;
    int tempIndex;
    
    
    srand(time(NULL));
    
    // We generate all the posible numbers from where we can choose from.
    for(counter = 0; counter < bagSize; counter++)
	bagOfNumbers[counter] = counter;

    // This is the main loop
    for(counter = 0; counter < numberDigits; counter++) {

	// We pick a number from the bagOfNumbers by selecting
	// a valid index
	randomIndex = rand() % bagSize;
	generatedNumbers[counter] = bagOfNumbers[randomIndex];

	// After choosing one, we remove that number by moving downwards
	// the rest of the numbers. And we shrink the bagSize by one.
	// Now its imposible to pick again the same number, even if
	// the same index comes up.
	for(tempIndex = randomIndex; tempIndex < bagSize - 1; tempIndex++) {
	    bagOfNumbers[tempIndex] = bagOfNumbers[tempIndex+1];
	}

	bagSize--;

    }

    // Important, no memory leaking :D
    free(bagOfNumbers);

    // Remember to free this pointer later
    return generatedNumbers;

}

Cheers!

Dark_Helmet · 08-22-2006, 10:13 AM

I like that approach as well. I'd also like to offer a couple improvements if I may.

Have the function check numberDigits against bagSize to make sure it's even possible to create a unique number (e.g. it's impossible to create a number with 11 unique digits when there are only 10 unique digits in the set).

Second, rather than shifting all the elements of bagOfNumbers down each time, just overwrite the number at the randomly selected index with the last element that could have been picked (i.e. not the last element in the array). Something like this:

Code:

bagOfNumbers[randomIndex] = bagOfNumbers[bagSize];
bagSize--;

But these are, admittedly, minor changes to the function.

demon_vox · 08-22-2006, 01:00 PM

Code:

bagOfNumbers[randomIndex] = bagOfNumbers[bagSize];
bagSize--;

NOOOOOOOO! I hate when this simple elegant solutions doesnt come from my brain

Dark_Helmet thats a big improvement since it makes it far more clear plus it works with better performance, so I have to congratulate you for that

As regard the other improvement, it's something I didnt think of, because I tought it from another perspective. I wanted to make a function that creates a unique sequence from a set of numbers, not just digits. Then the numbers could represent anything. Besides if I want to make an hexadecimal sequence I would need up to the number 16, even though its not just a digit.
But of course, that was something else that I wanted to add which was not part of the problem.

Cheers and good improvement of yours (which I will ovbiously store in my memory for later usage

)