Scegli m elementi in modo casuale da un vettore contenente n elementi

Question

Ho un vettore contenente elementi n. Devo scegliere un sottoinsieme di elementi m in modo casuale dal vettore senza ripetizione. Qual è il modo più efficace per farlo? Ho bisogno di farlo diverse migliaia di volte nel mio codice.

La soluzione in cima alla mia mente è quello di utilizzare rand() per generare un numero casuale tra k0 e n. Quindi seleziona l'elemento nel vettore e inseriscilo in un std::set. Continuate a farlo fino a quando le dimensioni del set diventano uguali a m. Ora ho la certezza che il set contiene m elementi unici scelti casualmente dal set di elementi n.

Quali sono le altre soluzioni possibili?

Grazie.

Answer 1

Volete un Fisher-Yates shuffle (fermata dopo iterazioni 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 a http://ideone.com/3A3cv. Questo è significativamente più veloce di std::random_shuffle quando sono necessari solo pochi numeri casuali dal set e dovrebbe essere quasi della stessa velocità anche se N==M.

Answer 2

Un modo che si possa fare è quello di creare una lista di tutti gli indici del vettore, mescolarle, e prendere la prima n di essere gli indici degli oggetti selezionati:

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