Comment obtenir un élément aléatoire à partir d'un conteneur C++ ?

Question

Quelle est la bonne façon d'obtenir un élément [pseudo-]aléatoire à partir d'une plage STL ?

Le mieux que je puisse faire est de faire std::random_shuffle(c.begin(), c.end()) et ensuite prendre mon élément aléatoire dans c.begin() .

Cependant, je pourrais vouloir un élément aléatoire à partir d'un const ou je ne veux peut-être pas payer le coût d'un mélange complet.

Y a-t-il un meilleur moyen ?

Answer 1

J'ai posté cette solution sur un article de Google+ où quelqu'un d'autre y faisait référence. Je la poste ici, car celle-ci est légèrement meilleure que les autres car elle évite les biais en utilisant la distribution std::uniform_int_distribution :

#include  <random>
#include  <iterator>

template<typename Iter, typename RandomGenerator>
Iter select_randomly(Iter start, Iter end, RandomGenerator& g) {
    std::uniform_int_distribution<> dis(0, std::distance(start, end) - 1);
    std::advance(start, dis(g));
    return start;
}

template<typename Iter>
Iter select_randomly(Iter start, Iter end) {
    static std::random_device rd;
    static std::mt19937 gen(rd());
    return select_randomly(start, end, gen);
}

L'exemple d'utilisation est :

#include <vector>
using namespace std;

vector<int> foo;
/* .... */
int r = *select_randomly(foo.begin(), foo.end());

J'ai fini par créer un gist avec un meilleur design suivant une approche similaire .

Answer 2

C++17 std::sample

Il s'agit d'une méthode pratique pour obtenir plusieurs éléments aléatoires sans répétition.

main.cpp

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

int main() {
    const std::vector<int> in{1, 2, 3, 5, 7};
    std::vector<int> out;
    size_t nelems = 3;
    std::sample(
        in.begin(),
        in.end(),
        std::back_inserter(out),
        nelems,
        std::mt19937{std::random_device{}()}
    );
    for (auto i : out)
        std::cout << i << std::endl;
}

Compilez et exécutez :

g++-7 -o main -std=c++17 -Wall -Wextra -pedantic main.cpp
./main

Sortie : 3 nombres aléatoires sont choisis parmi 1, 2, 3, 5, 7 sans répétition.

Par souci d'efficacité, seuls O(n) est garantie puisque ForwardIterator est l'API utilisée, mais je pense que les implémentations de stdlib vont se spécialiser pour O(1) lorsque cela est possible (par exemple vector ).

Testé dans GCC 7.2, Ubuntu 17.10. Comment obtenir GCC 7 en 16.04 .

Answer 3

Toutes les réponses utilisant % ici sont incorrects, puisque rand() % n produira des résultats biaisés : imaginez RAND_MAX == 5 et le nombre d'éléments est 4. Alors vous obtiendrez deux fois plus les chiffres 0 et 1 que les chiffres 2 ou 3.

Une façon correcte de procéder est la suivante :

template <typename I>
I random_element(I begin, I end)
{
    const unsigned long n = std::distance(begin, end);
    const unsigned long divisor = (RAND_MAX + 1) / n;

    unsigned long k;
    do { k = std::rand() / divisor; } while (k >= n);

    std::advance(begin, k);
    return begin;
}

Un autre problème est que std::rand est seulement supposé avoir 15 bits aléatoires, mais nous l'oublierons ici.

Answer 4

Cela fonctionne bien tant que RAND_MAX est beaucoup plus grande que la taille du conteneur, sinon elle souffre du problème de biais cité par Alexandre :

vector<int>::iterator randIt = myvector.begin();
std::advance(randIt, std::rand() % myvector.size());

Answer 5

Si vous ne pouvez pas accéder à la taille, je pense que vous devriez faire ce qui suit. Elle renvoie l'itérateur vers l'élément aléatoire.

#include <algorithm>
#include <iterator>

template <class InputIterator> InputIterator 
random_n(InputIterator first, InputIterator last) {
   typename std::iterator_traits<InputIterator>::difference_type distance = 
        std::distance(first, last);
   InputIterator result = first;
   if (distance > 1) {
      // Uses std::rand() naively.  Should replace with more uniform solution. 
      std::advance( result, std::rand() % distance );
   }
   return result;
}
// Added in case you want to specify the RNG.  RNG uses same 
// definition as std::random_shuffle
template <class InputIterator, class RandomGenerator> InputIterator 
random_n(InputIterator first, InputIterator last, RandomGenerator& rand) {
   typename std::iterator_traits<InputIterator>::difference_type distance = 
       std::distance(first, last);
   InputIterator result = first;
   if (distance > 1) {
      std::advance( result, rand(distance) );
   }
   return result;
}