¿Cómo obtener un elemento aleatorio de un contenedor de C ++?

¿Cuál es una buena manera de obtener un elemento [pseudo-] aleatorio de un rango STL?

Lo mejor que se me ocurre es hacer std::random_shuffle(c.begin(), c.end()) y luego tomar mi elemento aleatorio de c.begin() .

Sin embargo, es posible que desee un elemento aleatorio de un contenedor const , o puede que no quiera el costo de una mezcla completa.

¿Hay una mejor manera?

Todas las respuestas que usan % aquí son incorrectas, ya que rand() % n producirá resultados parciales: imagina RAND_MAX == 5 y la cantidad de elementos es 4. Luego obtendrás dos veces más el número 0 y 1 que los números 2 o 3.

Una forma correcta de hacer esto es:

 template  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; } 

Otro problema es que std::rand solo se supone que tiene 15 bits aleatorios, pero lo olvidaremos aquí.

Publiqué esta solución en un artículo de Google+ donde alguien más hizo referencia a esto. Publicarlo aquí, ya que este es ligeramente mejor que otros porque evita el sesgo mediante el uso de std :: uniform_int_distribution:

 #include  #include  template 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 Iter select_randomly(Iter start, Iter end) { static std::random_device rd; static std::mt19937 gen(rd()); return select_randomly(start, end, gen); } 

El uso de la muestra es:

 #include  using namespace std; vector foo; /* .... */ int r = *select_randomly(foo.begin(), foo.end()); 

Terminé creando una esencia con un mejor diseño siguiendo un enfoque similar .

C ++ 17 std::sample

Este es un método conveniente:

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

Por eficiencia, solo O(n) está garantizado ya que ForwardIterator es la API utilizada, pero creo que las implementaciones stdlib se especializarán en O(1) cuando sea posible (por ejemplo, vector ).

Probado en g++ 7.2, con g++ -std=c++17 , Ubuntu 17.10.

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

Si no puede acceder al tamaño, creo que le gustaría hacer lo siguiente. Devuelve el iterador al elemento aleatorio.

 #include  #include  template  InputIterator random_n(InputIterator first, InputIterator last) { typename std::iterator_traits::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  InputIterator random_n(InputIterator first, InputIterator last, RandomGenerator& rand) { typename std::iterator_traits::difference_type distance = std::distance(first, last); InputIterator result = first; if (distance > 1) { std::advance( result, rand(distance) ); } return result; } 

Tome la cantidad de elementos, c.size() , luego obtenga un random_number entre 0 y c.size() , y use:

 auto it = c.begin(); std::advance(it, random_number) 

Eche un vistazo a http://www.cplusplus.com/reference/clibrary/cstdlib/rand/

Puede tratar de obtener un número aleatorio entre 0 y la cantidad de elementos del contenedor. A continuación, puede acceder al elemento correspondiente del contenedor. Por ejemplo, puedes hacer esto:

 #include  #include  // ... std::srand(std::time(0)); // must be called once at the start of the program int r = std::rand() % c.size() + 1; container_type::iterator it = c.begin(); std::advance(it, r); 

Puede usar 0 ~ 1 función aleatoria para generar un número flotante para cada elemento en el contenedor como su puntaje. Y luego seleccione el que tenga el puntaje más alto.