Get random number without repeating

[alexchen]

I am trying to get a random number without repeating.

int r,number;


srand(time(NULL));
number=10;
r=rand() % number+1;

[ravenous]

OK. Do you have a problem that you don't know how to solve? Or a question that needs to be answered? If so, you might need to post a few more details before anyone can help you.

What do you mean by "without repeating"? If you want random numbers between 0 and 10, then there is quite likely to be repetition of the numbers quite quickly, since each number has about a 9% chance of coming up with any given call to rand() .

[myk45]

@OP

Is this what you mean?

Use a visited[] array to mark the ones that have already been generated.

int visited[100]; // to mark visited ones. Let all of the values be 0 initially.
int count = 0;

// Now, lets try to store 10 unique numbers between 0-99
while (count < 10) {
        num = rand() % 100;
   
        // check if num has already been generated
        if ( visited[num] == 0 ) {
               // now mark it as visited
               visited[num] = 1;
               num_array[count++] = num;  // store the generated number in an array.
        }
}

PS: This does not generate random numbers uniquely, we are storing values that are not repeating.

[ravenous]

Another way you could do this is by making a std::vector of length 100, if we're getting unique numbers between 0 and 99, and then using the std::vector::erase method:

const unsigned range = 100;
const unsigned numberToSelect = 10;
std::vector< unsigned > remainingNumbers(range);
std::vector< unsigned > chosenNumbers(numberToSelect);

/* Initialise the list of possible choices */
for(unsigned i = 0; i < range; i++)   remainingNumbers[i] = i;

/* Now chose however many you want, without repeats */
for(unsigned i = 0; i < numberToSelect; i++){
   /* Generate a random number to select */
   int selectedElement = rand()%(range - i);

   /* Put it in the chosenNumbers vector */
   chosenNumbers[i] = remainingNumbers[selectedElement];

   /* Now erase this number from the possible numbers, so that it can't be chosen again */
   remainingNumbers.erase(remainingNumbers.begin() + selectedElement);
}

This method has the disadvantage that erasing elements of a vector is a relatively slow operation, but the advantage that it will run in a roughly constant amount of time. There should also be some sanity checking, to make sure that numberToSelect < range etc. You could also make it more efficient at generating large sets of unique numbers by checking if the requested number of elements is greater than half of the range and then swapping the remainingNumbers and the chosenNumbers vectors over :o)

[WaltP]

Oh, ghod! Another one of those ridiculous suggestions to a student use a vector instead of an array. A vector is a higher level object and if you can't use an array properly, vectors are not the solution. The solution is to learn to use an array! Learn vectors when you understand the easy stuff!

[ravenous]

An array-based solution was already posted above, I was just trying to give some other options :o) People are free to take them or leave them, I guess. I suppose you could use an array for a method like this and just move all the elements about by hand:

const unsigned range = 100;
const unsigned numberToSelect = 10;
unsigned *remainingNumbers = new unsigned[range];
unsigned *chosenNumbers = new unsigned[numberToSelect];
 
/* Initialise the list of possible choices */
for(unsigned i = 0; i < range; i++)   remainingNumbers[i] = i;
 
/* Now chose however many you want, without repeats */
for(unsigned i = 0; i < numberToSelect; i++){
   /* Generate a random number to select */
   int selectedElement = rand()%(range - i);
 
   /* Put it in the chosenNumbers vector */
   chosenNumbers[i] = remainingNumbers[selectedElement];
 
   /* Now erase this number from the possible numbers, so that it can't be chosen again */
   for(unsigned j = selectedElement; j < range - i - 1; j++)
      remainingNumbers[j] = remainingNumbers[j + 1];
}

/* Do things with the chosen numbers */

/* tidy up */
delete[] remainingNumbers;
delete[] chosenNumbers;

Actually, the total number of elements (chosen + remaining) is constant, so you could use the elements at the end to store the chosen ones:

const unsigned range = 100;
const unsigned numberToSelect = 10;
unsigned *numbers = new unsigned[range];
 
/* Initialise the list of possible choices */
for(unsigned i = 0; i < range; i++)   remainingNumbers[i] = i;
 
/* Now chose however many you want, without repeats */
for(unsigned i = 0; i < numberToSelect; i++){
   /* Generate a random element to select, from the range of elements remaining */
   int selectedElement = rand()%(range - i);
 
   /* Remember the value of the chosen element */
   unsigned temp = remainingNumbers[selectedElement];
 
   /* Now move this number to the end, so that it can't be chosen again */
   for(unsigned j = selectedElement; j < range - i - 1; j++)
      remainingNumbers[j] = remainingNumbers[j + 1];
      
   /* Put the chosen number at the end of the array */
   numbers[range - i - 1] = temp;
}

/* Do things with the chosen numbers */

/* tidy up */
delete[] numbers;

Then you can access the chosen numbers by looking at the last numberToSelect elements of the numbers array. I think I might actually prefer this to my original suggestion.

Of course, we still don't know if the original post was anything to do with this at all :o)

[StuXYZ]

Sorry the solution given is just too inefficient. You simple don't need to copy the whole array each time.

Taking ravenous's code base:

const unsigned int range = 100;
const unsigned int numberToSelect = 10;


int* remainingNumbers = new int[range];
int* chosenNumbers = new int[numberToSelect];
 
// Initialise the list of possible choices
for(int i = 0; i < range; i++)   
  remainingNumbers[i] = i;
 
for(int i = 0; i < numberToSelect; i++)
  {
    const int selectedElement = rand() % (range - i);
    // Remember the value of the chosen element */
    chosenNumbers[i]=remainingNumbers[selectedElement]; 
  
    // Now: ONLY exchange the selected number with the last valid number
    // in the remainingNumbers set:
    remainingNumbers[selectedElement]=remainingNumbers[range-i-1];
}
delete [] remainingNumbers; 
/* Do things with the chosen numbers */

/* tidy up */
delete [] chosenNumbers;

That is more efficient. It still has the uniqueness, and is still equally likely to select all values. -- Just in case that this not
clear:
Consider the number 1-5

Array: 1 2 3 4 5
// select number 2 (from  rand % (5-0)
Array: 1 5 3 4 (5)         // 5 at the end if repeated since we copied it in
// select number 3 ( from rand % (5-1)   -- you can't get the last number in the array.
Array: 1 5 4 (4) (5)       // 4 and 5 repeated
// select 5           // FROM position [1] from rand % (5-2)
Array: 1 4 (4) (4) (5) 
/// etc....

Can I also say that it is normally a bad idea to use rand() for just about anything were a high level of randomness is required. Use something like the MersenneTwister code. rand(), especially were you are getting the low level bits with a % operator, is particular highly correlated.

If you don't want repeats in a very large set -- were having an array of all the numbers would be prohibative, the there are a couple of pseudo-random non-repeating sequences that can be used. E.g. http://www.usenix.org/event/usenix99/full_papers/deraadt/deraadt_html/node17.html

Additionally, you can roll your own version, since many [not all] RNG are actually non-repeating, but normally on a 2^32 or greater basis. You can reduce the size of the bits in the table down to n where n is chosen to be the smallest n that 2^n is greater than the range you need. Then just discard all numbers outside your chosen range. That way you only discard at most 1 in 2 numbers on a full range selection. [However, it take some serious math's ability to ensure that you have a "good" random number generator still -- Ability that I definitely don't have. ]

[ravenous]

Very nice. Swapping the selected element and the last element is definitely a more elegant solution :o) If you wanted to only use one array (as in the second method) then you could also do:

for(unsigned i = 0; i < numberToSelect; i++){
   const int selectedElement = rand()%(range - i);
   const int temp = numbers[selectedElement];
   numbers[selectedElement] = numbers[range - i - 1];
   numbers[range - i - 1] = temp;
}

I agree, that I generally wouldn't use rand() if you want a high degree of randomness.