choose random vector entry

[PhysicsIsFun]

Hi guys,

is there an easy way to choose an integer between 0 and N?
To be more precise, I want to randomly(!) choose an element from a vector, so I thought I would use a uniformly distributed random integer as vector index.


Regards

[Ganado]

Yes.

#include <iostream>
#include <random>
#include <chrono>
#include <vector>

int main ()
{
    // obtain a seed from the system clock:
    unsigned seed = std::chrono::system_clock::now().time_since_epoch().count();
    std::mt19937 gen(seed); // mt19937 is a standard mersenne_twister_engine

    int n;
    std::cout << "enter n: ";
    std::cin >> n;
    // closed-interval uniform distribution: [0, n-1]
    std::uniform_int_distribution<int> random_index(0, n-1);

    std::vector<int> vec(n);
    for (int i = 0; i < n; i++)
    {
        // put some dummy values in
        vec[i] = 1 + (i*i) % n;
    }

    int index = random_index(gen);
    std::cout << "Random index: " <<  index << "\n";
    std::cout << "vec[" << index << "] == " << vec[index] << std::endl;
}

enter n: 100
Random index: 77
vec[77] == 30 

[Handy Andy]

Hello PhysicsIsFun,

Yes it is possible.

Before you access the vector use whatever random number generator you wish. Then use the result as the index of the vector. You may also be able to use the call to the RNG as the index of the vector.

Andy

[icy1]

nice1 from Ganado. Also it should be noted if you'd like to continuously produce random, non-repeating, elements from a vector (e.g. dealing from a deck of cards), you could simply std::shuffle the vector and then access its elements normally from the top. You could even incorporate a specific randomizing engine into the shuffle.
Edit: can also use Ganado's Mersenne Twister in there with similar syntax

brief example

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

using namespace std;

int main()
{
    random_device rd;
    default_random_engine rng { rd() };
    //mt19937 rng { rd() };    // or uncomment this for a Mersenne Twister

    vector<int> v { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 };
    shuffle(v.begin(), v.end(), rng);
    for (auto& ele : v)
        cout << ele << ' ';
    cout << '\n';

    return 0;
}

possible output

7 3 6 8 2 11 5 9 10 1 12 4 

[PhysicsIsFun]

Thanks for the responses!

@Ganado
Seems to be a good example according to icy1's comment.

However, I don't really understand the code. That's not what I understand as 'easy' =(
I don't know what a seed is, what a mersenne_twister_engine is or what uniform_int_distribution does.

[Ganado]

Feel free to use icy1's code as well, or a combination of our code.

The three things you listed are just boilerplate, you don't need to understand the details, but should understand what they do at a higher-level.

seed - an initial value given to the random number generator that it then produces a sequence of pseudo-random numbers for. In this case, we're using the number of seconds since epoch time. You can use random_device as the equivalent seed as well (but strangely on my machine, g++ always produces the same sequence of numbers for me, so I use a time seed).

std::mt19937 is a type of random number generator. The algorithm is complicated, but you don't need to understand it (I don't understand it either). But you need a generator to make random numbers.

uniform_int_distribution is the most important piece of information.
Line 16 defines the distribution, which is in range [0, n-1].
A different random index is generated every time you call random_index(gen). You pass the RNG into the distribution, to get a random value from that distribution.
In your OP, you said "I would use a uniformly distributed random integer", so I assume you know what "uniform" means.

[PhysicsIsFun]

@Ganado

Thanks for the detailed explanation!

seed: From a bit of google'ing I understand that the seed is necessary so that the generator does not always create the same sequence of numbers from which he picks a random number?

mt19937: alright, I don't need to understand the inner mechanism.
I need all of this in a program for an academic project. What could I write in my report?
"This function is a random number generator that randomly picks a number from a the distribution to whom it was passed over"?

uniform_int_distribution:
Yes, uniformity is needed as I don't want to pick one vector index with greater probability than another.

I think I understand the essential parts then.
Just a few more general questions, because I haven't taken a deeper look at classes and such.

If I am using namespace std, all the "std::" in your code can be left out, right?
Also you included the templates "Random" and "Chrono". Can you explain this line:
unsigned seed = std::chrono::system_clock::now().time_since_epoch().count();
Is chrono a class that I can use due to the template "chrono"?
And is it necessary to write chrono:: even though I have included the template?

I assume mt19937 is a class from <random>?
The std:: also implies it is part of the standard library. I always thought templates are included to expand the standard library. E.g. that vectors are not part of the standard library, thus one has to #include them?

Sorry for these noob questions, in my ebook I still have to reach the object oriented stuff and the templates. (still have to write my code...)

[Ganado]

I'll attempt to answer.

What could I write in my report? "This function is a random number generator that randomly picks a number from a the distribution to whom it was passed over"

"The std::mt19937 class is the C++ implementation of the Mersenne Twister, a widely used general-purpose pseudorandom number generator (PRNG)." That's how I would personally word it.
https://en.wikipedia.org/wiki/Mersenne_Twister

If I am using namespace std, all the "std::" in your code can be left out, right?

Yes. You can use "using namespace std;", although the devil is in the detail, because it dumps the entire namespace into your code. Misusing "using namespace std;" can cause naming conflicts if you define functions or other classes/objects that become ambiguous when already defined in the std namespace. It's up to you, just be aware of what you're doing.
https://stackoverflow.com/questions/1452721/why-is-using-namespace-std-considered-bad-practice

Also you included the templates "Random" and "Chrono"

I think you're misusing terminology here.
When you "#include <name>", you're not necessarily including a template definition, you're including a header file. A header file contains the declarations/definitions of classes/functions/objects so that you, the user of those items, can have access to them.
See: https://en.wikipedia.org/wiki/Include_directive
C++ standard library header files often contain templates, but they don't have to. It's two separate concepts.

Is chrono a class that I can use due to the template "chrono"?

chrono is not a class or a template, it's a namespace, and also the name of the header file that contains definitions of useful date and time utilities, which are defined in the std::chrono namespace.
https://en.cppreference.com/w/cpp/chrono
https://www.geeksforgeeks.org/namespace-in-c/

Simplified example:

namespace std {
    namespace chrono {
        class system_clock {
            // etc.
        };
    }
}

And is it necessary to write chrono:: even though I have included the template?

I would keep the chrono:: in your code, but you could get rid of it by doing
using namespace std::chrono;... but I don't recommend getting in the habit of doing that.

assume mt19937 is a class from <random>?

Yes, mt19937 is a class defined in the <random> header file.

The std:: also implies it is part of the standard library.

Yes.

E.g. that vectors are not part of the standard library, thus one has to #include them?

No. It's all part of the C++ standard library. std::vector. To get anything from the standard library, you need to #include something. Whether that's <vector> or <iostream> or <cstdlib>, etc.

Hope that clears some things up.

[PhysicsIsFun]

Thank you again, Ganado!

unsigned seed = std::chrono::system_clock::now().time_since_epoch().count();
So seed is a datatype?
So inside namespace std there is a namespace chrono, and in there is another namespace named system_clock. In there, there is a now() function. What do the " . " do between the three methods in the end?

Also, what about this one?

seed: From a bit of google'ing I understand that the seed is necessary so that the generator does not always create the same sequence of numbers from which he picks a random number?

[Ganado]

So seed is a datatype

Not sure what you mean. seed is the name of the variable there. The type of the variable is unsigned (AKA unsigned int).

and in there is another namespace named system_clock

system_clock is a class, not a namespace.
https://en.cppreference.com/w/cpp/chrono/system_clock
https://en.cppreference.com/w/cpp/chrono/system_clock/now

What do the " . " do between the three methods in the end?

The dot operator is how you commonly access members of a class.

class Foo {
  public:
    void Bar() {}
};

int main()
{
    Foo foo;
    foo.Bar(); // accesses the method of Foo
}

system_clock::now() returns an object of type time_point.
https://en.cppreference.com/w/cpp/chrono/system_clock/now
https://en.cppreference.com/w/cpp/chrono/time_point

time_since_epoch() returns a duration object
https://en.cppreference.com/w/cpp/chrono/time_point/time_since_epoch

seed: From a bit of google'ing I understand that the seed is necessary so that the generator does not always create the same sequence of numbers from which he picks a random number?

Yes. Different seeds will produce different sequences of pseudo-random numbers.

[PhysicsIsFun]

Not sure what you mean. seed is the name of the variable there. The type of the variable is unsigned (AKA unsigned int).

Ahh... did not know one could skip the "int" in "unsigned int", so I assumed "unsigned seed" was some kind of special data type for the random functions :D"

system_clock is a class, not a namespace.
The dot operator is how you commonly access members of a class.
system_clock::now() returns an object of type time_point.

Ok, system_clock is a class. But why do I need the "::" operator there to access the member function now(), not the "." like in your example?

And does "now().time_since_epoch.count()" imply that count is a member of time_since_epoch and time_since_epoch is a member of now()? Although I don't think one would call it "member", since now() is not a class, but a function itself.

Yes. Different seeds will produce different sequences of pseudo-random numbers.

Thanks!

[icy1]

https://en.cppreference.com/w/cpp/chrono/system_clock/now

std::chrono::system_clock::now().time_since_epoch().count();

now() is a static method, so can be accessed from the class directly (as opposed to through an instance of that class)
It returns something called a std::chrono::time_point . On this returned item , the time_since_epoch() member function is called, which now returns a std::chrono::duration. Then on this returned item (duration), count() member function is called.

@PhysicsIsFun -- Honestly, Ganado added all these links already... did you even click and read them?

And does "now().time_since_epoch.count()" imply that count is a member of time_since_epoch and time_since_epoch is a member of now()? Although I don't think one would call it "member", since now() is not a class, but a function itself.

A class does not necessarily own what it is returning. It may just be creating and returning a new one of those objects, for example.

[PhysicsIsFun]

@icy1
Of course I take a look at them, but they don't answer the question on their own. Like, your link does not say what you have just written.

now() is a static method, so can be accessed from the class directly (as opposed to through an instance of that class)

Ok, so that's why I need the "::" there instead of the "." .

It returns something called a std::chrono::time_point . On this returned item , the time_since_epoch() member function is called, which now returns a std::chrono::duration. Then on this returned item (duration), count() member function is called.

Ahh... so now() returns another class, and time_since_epoch() is simply a member function of this class which is why I need the "." operator.
I think I get it now, thanks :)

[MikeyBoy]

Ahh... so now() returns another class

now() returns an object. It's worth understanding the difference between an object, and a class. That difference is crucial in understanding, for example, the difference between using :: and using . that you were struggling with a few posts up.

[PhysicsIsFun]

@MikeyBoy
After quick Google: An object is simply an instance of a class.

Ganado wrote:

system_clock::now() returns an object of type time_point.

So now() is a static method that can be called from a class.
It returns a concrete realization of the class time_point.
To use the member function of that returned object, I need to use "." .

That's why it is
system_clock::now().time_since_epoch()

Do I have it right now??

[kingkush]

Another way to do it if you don't want to learn about seeding and rand() just yet. But i was strongly suggest using rand() and seeding with time.

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

int main()
{
    std::vector<int> intVect;
    for(int i = 0; i < 15; i++)
    {
        intVect.push_back(i);
    }
    std::random_shuffle(intVect.begin(), intVect.end());
    for(int i = 0; i < intVect.size(); i++)
    {
        std::cout << intVect[i] << std::endl;
    }
}

Downside to this code is when it execute the numbers will be in the same order after shuffling. Meaning if you put 1,2,3 and shuffled and got 2,3,1 you will always get 2,3,1 when shuffling 1,2,3.

[Ganado]

rand() isn't always uniform, has the pidgeon hole problem when combined with modulo, and it's the crusty old C way of doing it anyway. That being said, I agree it might be easier for beginners to understand, since it avoids C++11 stuff.

However, your code is deprecated. void random_shuffle( RandomIt first, RandomIt last ); was deprecated in C++14, and I just learned it was actually removed in C++17.
https://en.cppreference.com/w/cpp/algorithm/random_shuffle

Use std::shuffle instead, like icy1's example.

[kingkush]

Yes the code i used is definitely dated. I believe c++98 but i find it easier to understand older code when first learning and then looking up the newer methods. That way I'm not completely lost and understand at least the basics.

But yes i do completely agree if you understand icy1's example that is currently the best and easiest way to do it if you're looking to shuffle the vector.

[Ganado]

i find it easier to understand older code when first learning

True. Sometimes I'll still just make a rand() call when testing something quick because that's so much easier to memorize/type. I wish C++'s <random> library had the option of being more like C#'s or Java's. Needing a separate object for each distribution range is weird.

[MikeyBoy]

Do I have it right now??

Yep :)