Random number generation from a vector of numbers

Question

I have a vector v = {1,5,4,2}. Now I want to write a function that returns a random pair of numbers from this vector. Example: {1,2},{4,4},{2,5},{5,1},{1,5},{2,2}....... I want this pair to be generated in a random manner. Any idea how to implement this ?

Answer 1

auto pair = std::make_pair(v[rand() % v.size()], v[rand() % v.size()]);

is one way.

Switch out rand() to something from the new <random> library of C++11 if you require the generator to have better statistical properties: aside from the generator itself, the use of % can introduce a statistical bias.

Answer 2

It depends on whether you want to guarantee that the two items are distinct or not (i.e. are you allowed to draw the same item twice?)

Here's a solution and demo for both requirements:

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


template<class Rnd, class Iter>
auto random_iterator(Rnd&& rnd, Iter first, Iter last)
{
    assert(first != last);
    std::size_t size = std::distance(first, last);
    auto dist = std::uniform_int_distribution<std::size_t>(0, size - 1);
    auto i = dist(rnd);
    return std::next(first, i);
}

template<class Iter>
auto remove_iter(Iter last, Iter to_remove)
{
    --last;
    std::iter_swap(last, to_remove);
    return last;
}

// precondition: !vec.empty()
template<class Rnd, class T> 
auto select_random_pair(Rnd&& device, std::vector<T> const& vec)
{
    auto first = begin(vec), last = end(vec);

    // care - we are returning references
    auto& a = *random_iterator(device, begin(vec), end(vec));
    auto& b = *random_iterator(device, begin(vec), end(vec));

    return std::tie(a, b);
}

template<class Iter> 
auto make_index_vector(Iter first, Iter last)
{
    auto indices = std::vector<std::size_t>(std::distance(first, last));
    std::iota(begin(indices), end(indices), std::size_t(0));
    return indices;
}

// precondition: vec.size() >= 2
template<class Rnd, class T> 
auto select_distinct_random_pair(Rnd&& device, std::vector<T> const& vec)
{
    auto indices = make_index_vector(begin(vec), end(vec));
    auto first = begin(indices), last = end(indices);

    auto a = *(last = remove_iter(last, random_iterator(device, first, last)));
    auto b = *random_iterator(device, first, last);


    return std::tie(vec[a], vec[b]);
}


int main()
{
    auto test_data = std::vector<int> { 1, 2, 3 };

    auto rng = std::random_device();

    const char* sep = "";
    auto emit = [&sep](std::tuple<int const&, int const&> tup)
    {
        std::cout << sep << "(" << std::get<0>(tup) << ", " << std::get<1>(tup) << ")";
        sep = ", ";
    };

    auto newline = [&sep] { std::cout << '\n'; sep = ""; };

    std::cout << "any:\n";
    for (int i = 0 ; i < 20 ; ++i)
    {
        emit(select_random_pair(rng, test_data));
    }

    newline();

    std::cout << "distinct:\n";
    for (int i = 0 ; i < 20 ; ++i)
    {
        emit(select_distinct_random_pair(rng, test_data));
    }

}

example output:

any:
(1, 2), (2, 3), (3, 1), (1, 1), (3, 1), (1, 2), (1, 1), (2, 1), (3, 3), (2, 3), (3, 3), (2, 2), (3, 1), (1, 2), (3, 2), (3, 2), (3, 2), (3, 1), (2, 3), (2, 3)
distinct:
(3, 2), (3, 2), (2, 3), (2, 1), (2, 3), (2, 3), (2, 1), (3, 2), (3, 2), (1, 3), (3, 2), (1, 2), (2, 1), (2, 1), (2, 3), (3, 1), (2, 3), (3, 2), (2, 1), (1, 3)