¿Cómo mezclar un std :: vector?

97

Estoy buscando una forma genérica y reutilizable de barajar un std::vectoren C ++. Así es como lo hago actualmente, pero creo que no es muy eficiente porque necesita una matriz intermedia y necesita saber el tipo de elemento (DeckCard en este ejemplo):

srand(time(NULL));

cards_.clear();

while (temp.size() > 0) {
    int idx = rand() % temp.size();
    DeckCard* card = temp[idx];
    cards_.push_back(card);
    temp.erase(temp.begin() + idx);
}
Laurent
fuente
nop. busque fisher-yates ....
Mitch Wheat
3
Trate de no usar rand(), hay mejores API de RNG disponibles (Boost.Random o 0x <random>).
Cat Plus Plus
Vinculado: stackoverflow.com/questions/147391/…
Sardathrion - contra el abuso SE

Respuestas:

201

Desde C ++ 11 en adelante, debería preferir:

#include <algorithm>
#include <random>

auto rng = std::default_random_engine {};
std::shuffle(std::begin(cards_), std::end(cards_), rng);

Live example on Coliru

¡Asegúrese de reutilizar la misma instancia de a lo rnglargo de múltiples llamadas a std::shufflesi tiene la intención de generar diferentes permutaciones cada vez!

Además, si desea que su programa cree diferentes secuencias de mezcla cada vez que se ejecuta, puede sembrar el constructor del motor aleatorio con la salida de std::random_device:

auto rd = std::random_device {}; 
auto rng = std::default_random_engine { rd() };
std::shuffle(std::begin(cards_), std::end(cards_), rng);

Para C ++ 98 puede usar:

#include <algorithm>

std::random_shuffle(cards_.begin(), cards_.end());
user703016
fuente
8
También puede conectar un generador de números aleatorios personalizado como tercer argumento de std::random_shuffle.
Alexandre C.
19
+1: tenga en cuenta que esto puede producir un resultado idéntico en cada ejecución del programa. Puede agregar un generador de números aleatorios personalizado (que se puede sembrar desde una fuente externa) como un argumento adicional std::random_shufflesi esto es un problema.
Mankarse
4
@ Gob00st: generará el mismo resultado para cada instancia del programa, no para todas las llamadas a random_shuffle. Este comportamiento es normal e intencionado.
user703016
3
@ TomášZato#include <algorithm>
user703016
4
@ ParkYoung-Bae Gracias, me acabo de enterar . Es realmente inconveniente cuando las respuestas SO no contienen información incluida porque están en la parte superior de los resultados de búsqueda de Google.
Tomáš Zato - Reincorpora a Monica el
10

http://www.cplusplus.com/reference/algorithm/shuffle/

// shuffle algorithm example
#include <iostream>     // std::cout
#include <algorithm>    // std::shuffle
#include <vector>       // std::vector
#include <random>       // std::default_random_engine
#include <chrono>       // std::chrono::system_clock

int main () 
{
    // obtain a time-based seed:
    unsigned seed = std::chrono::system_clock::now().time_since_epoch().count();
    std::default_random_engine e(seed);

    while(true)
    {
      std::vector<int> foo{1,2,3,4,5};

      std::shuffle(foo.begin(), foo.end(), e);

      std::cout << "shuffled elements:";
      for (int& x: foo) std::cout << ' ' << x;
      std::cout << '\n';
    }

    return 0;
}
Mehmet Fide
fuente
un mal ejemplo copiado de cplusplus.com/reference/algorithm/shuffle . ¿Cómo se hace otra llamada aleatoria?
miracle173
@ miracle173 ejemplo mejorado
Mehmet Fide
2
¿Por qué el uso extraño del reloj del sistema para una semilla en lugar de simplemente usarlo std::random_device?
Chuck Walbourn
6

Además de lo que dijo @Cicada, probablemente deberías sembrar primero,

srand(unsigned(time(NULL)));
std::random_shuffle(cards_.begin(), cards_.end());

Según el comentario de @ FredLarson:

la fuente de aleatoriedad para esta versión de random_shuffle () está definida por la implementación, por lo que no puede usar rand () en absoluto. Entonces srand () no tendría ningún efecto.

Entonces YMMV.


fuente
10
En realidad, la fuente de aleatoriedad para esta versión de random_shuffle()está definida por la implementación, por lo que es posible que no se use rand()en absoluto. Entonces srand()no tendría ningún efecto. Me he encontrado con eso antes.
Fred Larson
@Fred: Gracias Fred. No sabía eso. He estado acostumbrado a usar srand todo el tiempo.
6
Probablemente debería eliminar esta respuesta ya que es incorrecta y, lo que es peor, parece correcta y, de hecho, es correcta en algunas implementaciones, pero no en todas, lo que hace que este consejo sea muy peligroso.
Thomas Bonini
2
Como @Fred explicó anteriormente, lo que se random_shuffleusa para generar números aleatorios es la implementación definida. Esto significa que en su implementación usa rand()(y por lo tanto srand () funciona) pero en la mía puede usar algo totalmente diferente, lo que significa que en mi implementación incluso con srand cada vez que ejecuto el programa obtendré los mismos resultados.
Thomas Bonini
2
@Code: como comentamos, no funciona en todas las implementaciones. El hecho de que pueda proporcionar su propia generación de números no se menciona en su respuesta y no está relacionado con esta discusión en ningún caso. Siento que vamos en círculos: S
Thomas Bonini
2

Si está usando boost , puede usar esta clase ( debug_modeestá configurada en false, si desea que la aleatorización sea predecible entre la ejecución, debe configurarla en true):

#include <iostream>
#include <ctime>
#include <boost/random/mersenne_twister.hpp>
#include <boost/random/uniform_int.hpp>
#include <boost/random/uniform_int_distribution.hpp>
#include <boost/random/variate_generator.hpp>
#include <algorithm> // std::random_shuffle

using namespace std;
using namespace boost;

class Randomizer {
private:
    static const bool debug_mode = false;
    random::mt19937 rng_;

    // The private constructor so that the user can not directly instantiate
    Randomizer() {
        if(debug_mode==true){
            this->rng_ = random::mt19937();
        }else{
            this->rng_ = random::mt19937(current_time_nanoseconds());
        }
    };

    int current_time_nanoseconds(){
        struct timespec tm;
        clock_gettime(CLOCK_REALTIME, &tm);
        return tm.tv_nsec;
    }

    // C++ 03
    // ========
    // Dont forget to declare these two. You want to make sure they
    // are unacceptable otherwise you may accidentally get copies of
    // your singleton appearing.
    Randomizer(Randomizer const&);     // Don't Implement
    void operator=(Randomizer const&); // Don't implement

public:
    static Randomizer& get_instance(){
        // The only instance of the class is created at the first call get_instance ()
        // and will be destroyed only when the program exits
        static Randomizer instance;
        return instance;
    }

    template<typename RandomAccessIterator>
    void random_shuffle(RandomAccessIterator first, RandomAccessIterator last){
        boost::variate_generator<boost::mt19937&, boost::uniform_int<> > random_number_shuffler(rng_, boost::uniform_int<>());
        std::random_shuffle(first, last, random_number_shuffler);
    }

    int rand(unsigned int floor, unsigned int ceil){
        random::uniform_int_distribution<> rand_ = random::uniform_int_distribution<> (floor,ceil);
        return (rand_(rng_));
    }
};

Entonces puedes probarlo con este código:

#include "Randomizer.h"
#include <iostream>
using namespace std;

int main (int argc, char* argv[]) {
    vector<int> v;
    v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);
    v.push_back(6);v.push_back(7);v.push_back(8);v.push_back(9);v.push_back(10);

    Randomizer::get_instance().random_shuffle(v.begin(), v.end());
    for(unsigned int i=0; i<v.size(); i++){
        cout << v[i] << ", ";
    }
    return 0;
}
madx
fuente
¿Por qué estás usando tiempo para sembrar el generador en lugar de std::random_device?
Chuck Walbourn
1

Puede ser incluso más simple, la siembra se puede evitar por completo:

#include <algorithm>
#include <random>

// Given some container `container`...
std::shuffle(container.begin(), container.end(), std::random_device());

Esto producirá una nueva reproducción aleatoria cada vez que se ejecute el programa. También me gusta este enfoque debido a la simplicidad del código.

Esto funciona porque todo lo que necesitamos std::shufflees un UniformRandomBitGenerator, cuyos requisitos std::random_devicecumplen.

Nota: si baraja repetidamente, puede ser mejor almacenar el random_deviceen una variable local:

std::random_device rd;
std::shuffle(container.begin(), container.end(), rd);
Apollys apoya a Monica
fuente
2
¿Qué agrega esto que no formaba parte de la respuesta aceptada de hace 8 años?
ChrisMM
1
Todo lo que tiene que hacer es leer la respuesta para averiguarlo ... No hay mucho más que decir que no se haya explicado claramente anteriormente.
Apollys apoya a Monica el
1
La respuesta aceptada ya usa la reproducción aleatoria y dice que use random_device...
ChrisMM
1
La antigua respuesta aceptada podría ser más profunda. Sin embargo, esta es precisamente la respuesta de apuntar y disparar de una sola línea que esperaría al buscar en Google una pregunta tan simple sin mucho preámbulo. +1
Ichthyo
2
Esto está mal . random_deviceestá diseñado para ser llamado solo una vez para sembrar PRNG, no para ser llamado una y otra vez (lo que puede agotar la entropía subyacente rápidamente y hacer que cambie a un esquema de generación subóptimo)
LF