Elige m elementos al azar de un vector que contiene n elementos

Question

Tengo un vector que contiene n elementos. Necesito elegir un subconjunto de m elementos aleatoriamente del vector sin repetición. ¿Cuál es la forma más eficiente de hacer esto? Necesito hacer esto varias miles de veces en mi código.

La solución en la parte superior de la cabeza es utilizar rand() para generar un número aleatorio entre k0 y n. A continuación, elija el elemento k en el vector e insértelo en un std::set. Siga haciendo esto hasta que el tamaño del conjunto sea igual a m. Ahora estoy seguro de que el conjunto contiene m elementos únicos elegidos al azar del conjunto de elementos n.

¿Cuáles son las otras soluciones posibles?

Gracias.

Answer 1

¿Quieres una Fisher-Yates shuffle (parada después de iteraciones M):

template<class BidiIter > 
BidiIter random_unique(BidiIter begin, BidiIter end, size_t num_random) { 
    size_t left = std::distance(begin, end); 
    while (num_random--) { 
     BidiIter r = begin; 
     std::advance(r, rand()%left); 
     std::swap(*begin, *r); 
     ++begin; 
     --left; 
    } 
    return begin; 
} 

demo en http://ideone.com/3A3cv. Esto es significativamente más rápido que std::random_shuffle cuando solo necesita unos pocos números aleatorios fuera del conjunto, y debería ser casi la misma velocidad, incluso si N==M.

Answer 2

Una forma de poder hacer esto es crear una lista de todos los índices del vector, mezclarlas, y tomar la primera n ser los índices de los objetos seleccionados:

struct rangegenerator { 
    rangegenerator(int init) : start(init) { } 

    int operator()() { 
     return start++; 
    } 

    int start; 
}; 

vector<T> numbers; // this is filled somewhere else 

vector<int> indices(numbers.size()); 

generate(begin(indices), end(indices), rangegenerator(0)); 

random_shuffle(begin(indices), end(indices)); 

// then take the first n elements of indices and use them as indices into numbers