Generating a rand() %25 in which each number can only appear once

Question

I am trying to right a program, with arrays, which gets random numbers between 0 - 24 but they can only occur once. I know how to generate random numbers, I am just stuck on how to do the check to see if the number already exists in the array. I tried generating a new rand() % 25 and comparing it with placeholders in the array and if it didn't exist put the new random number in there but it did not work.

 void MultiU (){
         int size = 5;
         int array[5];
        srand(time(0));

        for (int index = 0; index < size; index++){
           exists[index] = rand() %25;
          }
    }

I am new to programming with arrays and rand(). I hope someone can guide me in the right direction.

Answer 1

std::unordered_set is your friend. It does not allow/insert duplicates, and you can exploit this fact to obtain 5 different numbers. When the set is of size 5, it is guaranteed to contain 5 different elements.

std::unordered_set<int> s;

while (s.size() < 5) {
    s.insert(rand() % 25);
}

Answer 2

Here's a general approach to getting lists of random numbers with no repeats:

#include <algorithm>
#include <iostream>
#include <random>
#include <vector>

int main() {
    std::vector<int> vals;
    for (size_t i = 0; i < 25; ++i) {
        vals.push_back(i);
    }
    std::shuffle(vals.begin(), vals.end(), std::mt19937());
    for (auto v : vals) {
        std::cout << v << std::endl;
    }
}

Here's a working demo.

In this case, it would be inefficient to do this and then only extract the first five numbers. However, as the list of possible random numbers gets larger (and you want to select more of them) this method will be more efficient than the one from The Paramagnetic Croissant.

I should also add that you should not use rand(). Or try to use rand() with a modulus to get fixed-range random numbers. They will not be properly distributed!

Answer 3

Below is the Pseudo code for what you are trying to do:- 1) First generate a random number

int number = rand() %25;

2) Check if "number" exists in array.

3) If not then insert else go to step 1;

Apart from that there are more lucrative options ( containers ) than plain array.

EDITED IN RESPONSE TO COMMENT#

You can define a function for this and call it in step 2 mentioned above:-

bool search ( int *p, int size, int element )
{
   for( int i = 0; i < size; i++ )
   {
     if ( *(p+i) == element )
     return false;
   }
   return true;
}

Hash-table would be very effective in this case if that's included in your class.

Answer 4

You may use Fisher–Yates_shuffle:

// Fisher–Yates_shuffle
std::vector<int> FisherYatesShuffle(std::size_t size, std::size_t max_size, std::mt19937& gen)
{
    assert(size < max_size);
    std::vector<int> res(size);

    for(std::size_t i = 0; i != max_size; ++i) {
        std::uniform_int_distribution<> dis(0, i);
        std::size_t j = dis(gen);
        if (j < res.size()) {
            if (i < res.size()) {
                res[i] = res[j];
            }
            res[j] = i;
        }
    }
    return res;
}

Live example

Answer 5

Check this code:

int numbers[26], tempNum; //Array required to store the used values and tempNum for the random number you want to generate
bool x; //This will be required later (true or false)
srand(time(0));//I think you have this clear

for(int i = 0; i <= 24; i++){//Required in order to generate 24 random numbers
        do{
        tempNum = (rand()%25);//Generates the random number

        x = false;//This sets the value as not used before
        for(int j =0; j <= 24; j++){//Scans the array to find out whether the value is used before
                if(tempNum == numbers[j]){//Tests if the value is used before
                           x = true;// If so marks it as used
                           }
                }
                }while(x == true);//This makes it go back to generating a new number part

        numbers[i] = tempNum;//This stores the number in the array
        cout << tempNum << endl;//Prints the number on the screen
}

Answer 6

The obvious solution is to create a vector with the acceptable values, do a random shuffle on it, and take the first n:

std::vector<int> values( 25 );
for ( int i = 0; i != 25; ++ i ) {
    values[i] = i;
}
std::random_shuffle( values.begin(), values.end() );
values.resize( size );

should do the trick.