Elija un subconjunto aleatorio exclusivo de un conjunto de valores únicos

Question

C++. Visual Studio 2010.

Tengo un std::vector V de N elementos únicos (heavy structs). ¿Cómo puede elegir M elementos aleatorios y únicos de manera eficiente?

E.g. V contiene 10 elementos: {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} y tomo tres ...

• 4, 0, 9
• 0, 7 , 8
• Pero NO esto: 0, 5, 5 < --- ¡no es único!

Se prefiere STL. Entonces, algo como esto?

std::minstd_rand gen; // linear congruential engine?? 
std::uniform_int<int> unif(0, v.size() - 1); 
gen.seed((unsigned int)time(NULL)); 

// ...? 

// Or is there a good solution using std::random_shuffle for heavy objects? 

Answer 1

Crear una permutación aleatoria de la gama 0, 1, ..., N - 1 y recoger la primera M de ellos; utilícelos como índices en su vector original.

una permutación aleatoria se hace fácilmente con la biblioteca estándar utilizando std::iota junto con std::random_shuffle:

std::vector<Heavy> v; // given 

std::vector<unsigned int> indices(V.size()); 
std::iota(indices.begin(), indices.end(), 0); 
std::random_shuffle(indices.begin(), indices.end()); 

// use V[indices[0]], V[indices[1]], ..., V[indices[M-1]] 

Puede suministrar random_shuffle con un generador de números aleatorios de su elección; verifique el documento ­ hombres ­ tación para más detalles.

Answer 2

La mayoría de las veces, el método proporcionado por Kerrek es suficiente. Pero si N es muy grande y M es de menor magnitud, se puede preferir el siguiente método.

Crea un conjunto de enteros sin signo y añádele números aleatorios en el rango [0, N-1] hasta que el tamaño del conjunto sea M. Luego usa los elementos en esos índices.

std::set<unsigned int> indices; 
while (indices.size() < M) 
    indices.insert(RandInt(0,N-1)); 

Answer 3

Ya que quería que fuera eficiente, creo que se puede conseguir una amortizados O(M), suponiendo que tiene para llevar a cabo esa operación muchas veces. Sin embargo, este enfoque no es reentrante.

Primero crea un vector local (es decir, static) de std::vector<...>::size_type (es decir, unsigned hará) valores.

Si introduce su función, cambiar el tamaño del vector para que coincida con N y llenarlo con los valores del tamaño mayor para N-1:

static std::vector<unsigned> indices; 
if (indices.size() < N) { 
    indices.reserve(N); 
    for (unsigned i = indices.size(); i < N; i++) { 
    indices.push_back(i); 
    } 
} 

Entonces, escoja al azar M números únicos de ese vector:

std::vector<unsigned> result; 
result.reserver(M); 
for (unsigned i = 0; i < M; i++) { 
    unsigned const r = getRandomNumber(0,N-i); // random number < N-i 
    result.push_back(indices[r]); 
    indices[r] = indices[N-i-1]; 
    indices[N-i-1] = r; 
} 

Ahora, el resultado está sentado en el vector result.

Sin embargo, todavía se tiene que reparar sus cambios a indices para la próxima ejecución, de modo que indices es monótona nuevo:

for (unsigned i = N-M; i < N; i++) { 
    // restore previously changed values 
    indices[indices[i]] = indices[i]; 
    indices[i] = i; 
} 

Pero este método sólo es útil, si tiene que ejecutar el algoritmo mucho y N no crece tanto que no puede vivir con indices comiendo RAM todo el tiempo.