How to create a vector of random numbers different between each other?-CodePudding

How could I efficiently fill a vector of elements containing random u- short ints which must be all different between each other?

(I already know how to fill a vector with random numbers using:

#include <iostream>
#include <random>
int main() {
    //INPUTs
    unsigned short int n_of_all_students, n_called_students;
    std::cout << "Enter how many students do you have: _";//(for example)
    std::cin >> n_of_all_students;
    std::cout << "Enter how many students you'd like to call: _";
    std::cin >> n_called_students;

    //SEED, ENGINE AND RANGE DEFINITIONs
    std::random_device random_device; // creates the seed
    std::mt19937_64 mt64{ random_device() }; //creates the engine (Mersenne Twister, 64 bit) and assignes to it the just created seed
    std::uniform_int_distribution<> al_range(1, n_of_all_students);//the range which the numbers will be created into

    //VECTOR FILLING
    std::vector<short int> called_students;
    for (auto i = 0; i < n_called_students;   i) {
        called_students.push_back(al_range(mt64));// puts, finally, the just generated random number into the vector

    //OUTPUT
    std::cout << i 1 << ":\t" << called_students[i] << '\n';
    }
}

, but I don't know how I could fill it only with different numbers

and I don't know neither if,

after that,

it would be more efficient to compare each number one between the other continuously replacing the equal ones with other random numbers until they are all different

or instead,

starting from an empty vector, to directly fill it with random different numbers)

Which one would be the most efficient solution?

How could I write it?

CodePudding user response：

A popular way to accomplish this for a reasonably small finite field of values is to simply generate the bed of possible values, then shuffle it, then draw off what you need.

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

int main() 
{
    unsigned short int n_of_all_students, n_called_students;
    std::cout << "Enter how many students do you have: ";
    std::cin >> n_of_all_students;
    std::cout << "Enter how many students you'd like to call: ";
    std::cin >> n_called_students;

    // build ids.
    std::vector<unsigned short int> ids(n_of_all_students);
    std::iota(ids.begin(), ids.end(), 1);

    // shuffle the ids
    std::mt19937_64 mt64{ std::random_device{}() };
    std::shuffle(ids.begin(), ids.end(), mt64);

    // pull the called count. 
    std::vector<unsigned short int> called_students(
        ids.begin(), std::next(ids.begin(), n_called_students) );
    std::sort(called_students.begin(), called_students.end());

    // print results.
    for (auto x :  called_students)
        std::cout << x << ' ';
    std::cout << '\n';
}

Input

Enter how many students do you have: 40
Enter how many students you'd like to call: 20

Output (varies, obviously)

1 2 4 5 9 12 13 16 22 23 24 26 27 28 29 31 34 35 37 39

another sample with the same input conditions:

2 3 8 9 12 13 14 17 19 21 22 23 26 29 31 32 35 36 38 40

Note: the sort is optional, but makes for a nice presentation.

This method is also known as "pulling from a hat", because the same method applies to "random" drawings. All the names are put in a hat, the hat is shaken about, and then the numbers are drawn without replacement.

Worth mentioning, the code above does NOT have a built-in-tragedy avoidance of someone asking to pull > N ids from a pool size of N. Obviously that isn't possible, and attempting to do so will invoke undefined behavior in the posted code without properly checking that n_called_students is less or equal to n_of_all_students, and that both are positive numbers. That cleanup I leave to you.

CodePudding user response：

It seems you want std::sample (C 17):

// build ids.
std::vector<unsigned short int> ids(n_of_all_students);
std::iota(ids.begin(), ids.end(), 1);

// sample the ids
std::mt19937_64 mt64{ std::random_device{}() };
std::vector<unsigned short int> called_students;
std::sample(ids.begin(), ids.end(),
            std::back_inserter(called_students),
            n_called_students,
            mt64);

Demo

CodePudding user response：

As other comment pointed out, the most efficient way to do that is filling the vector with the numbers you want to populate, then shuffle. you will need <algorithm> header, and std::shuffle() to do this:

#include <iostream>
#include <random>
#include <algorithm>
int main() {
    //INPUTs
    unsigned short int n_of_all_students, n_called_students;
    std::cout << "Enter how many students do you have: _";//(for example)
    std::cin >> n_of_all_students;
    std::cout << "Enter how many students you'd like to call: _";
    std::cin >> n_called_students;

    //SEED, ENGINE AND RANGE DEFINITIONs
    std::random_device random_device; // creates the seed
    std::mt19937_64 mt64{ random_device() }; //creates the engine (Mersenne Twister, 64 bit) and assignes to it the just created seed
    std::uniform_int_distribution<> al_range(1, n_of_all_students);//the range which the numbers will be created into

    //VECTOR FILLING
    std::vector<short int> called_students;
    for (auto i = 1; i <= n_of_all_students;   i) {
        called_students.push_back(i);// puts, finally, the just generated random number into the vector
    }
    std::shuffle(called_students.begin(), called_students.end(), mt64);
    //OUTPUT
    for(auto i=0; i<n_called_students;  i)
        std::cout << i   1 << ":\t" << called_students[i] << '\n';
}