¿Cómo seleccionar un elemento aleatorio en std :: set?

Question

¿Cómo puedo seleccionar un elemento aleatorio en un std::set?

ingenuamente intentado esto:

int GetSample(const std::set<int>& s) { 
    double r = rand() % s.size(); 
    return *(s.begin() + r); // compile error 
} 

Pero el operator+ no está permitido en esta forma.

Answer 1

Puede usar el método std::advance.

#include <set> 
#include <algorithm> 

int main() { 
    using namespace std; 
    // generate a set... 
    set<int> s; 
    for(int i = 0; i != 10; ++i) s.insert(i); 

    set<int>::const_iterator it(s.begin()); 

    // 'advance' the iterator 5 times 
    advance(it,5); 
} 

Answer 2

int GetSample(const std::set<int>& s) { 
    double r = rand() % s.size(); 
    std::set<int>::iterator it = s.begin(); 
    for (; r != 0; r--) it++; 
    return *it; 
} 

sería una manera de hacerlo, aunque no es bastante;

Answer 3

Si el acceso aleatorio es importante y puede vivir con un esfuerzo promedio de O (N) para la inserción, la solución dada en this paper podría ser conveniente.

La idea principal es utilizar un vector clasificado, y luego para buscar la función std::lower_bound. Esto, la búsqueda toma O (log N) como en un conjunto normal. Además, la inserción (aleatoria) toma O (N), ya que todos los elementos siguientes deben desplazarse al igual que en un vector normal (y posiblemente se realice una reasignación). Sin embargo, la inserción en la parte posterior es constante (a excepción de la reasignación. Puede evitar esto llamando al reserve() con un almacenamiento lo suficientemente grande).

Finalmente, el punto principal de la pregunta: El acceso aleatorio es O (1). Simplemente dibuje un número al azar i de una distribución uniforme en [0, V.size()-1], y devuelva el elemento correspondiente V[i].

Aquí está el código base del papel, que implementa este vector ordenado. Extenderlo según sea necesario:

template <class T, class Compare = std::less<T> > 
struct sorted_vector { 
using std::vector; 
using std::lower_bound; 
vector<T> V; 
Compare cmp; 
typedef typename vector<T>::iterator iterator; 
typedef typename vector<T>::const_iterator const_iterator; 
iterator begin() { return V.begin(); } 
iterator end() { return V.end(); } 
const_iterator begin() const { return V.begin(); } 
const_iterator end() const { return V.end(); } 

//...if needed, implement more by yourself 

sorted_vector(const Compare& c = Compare()) : V(), cmp(c) {} 
template <class InputIterator> 
sorted_vector(InputIterator first, InputIterator last, Const Compare& c = Compare()) 
: V(first, last), cmp(c) 
{ 
std::sort(begin(), end(), cmp); 
} 

//... 

iterator insert(const T& t) { 
    iterator i = lower_bound(begin(), end(), t, cmp); 
    if (i == end() || cmp(t, *i)) 
     V.insert(i, t); 
     return i; 
} 
const_iterator find(const T& t) const { 
    const_iterator i = lower_bound(begin(), end(), t, cmp); 
     return i == end() || cmp(t, *i) ? end() : i; 
} 
}; 

Para una aplicación más sofisticada, también se podría considerar this page.

EDITAR: o mejor aún, utilizar boost::container::flat_set, que implementa el conjunto utilizando la idea anterior, es decir, como un vector ordenado.

Answer 4

Primera Solución: O (log n) en el tiempo/ O (1) en el espacio

Una hipótesis en un comentario anterior, se puede hacer de O (log (no uniforme!) (n)) (vs O (n) para std::advance) sin un vector (usando O (n) espacio más) utilizando el método describo here.

Esencialmente, usted:

• cheque si el conjunto está vacío (si lo es, no hay esperanza)
• generar un valor aleatorio
• si ya no volver en otro insertarlo
• conseguir uno iterador it en él
• obtener el elemento de azar como *(it++) o *(set.begin())it si al final
• regreso no antes de eliminar el elemento que se inserta

N.B: Como ha señalado Aaron el elemento no se elige uniformemente al azar. Necesita construir el elemento aleatorio con la misma distribución que los elementos en el conjunto para aproximarse a un sondeo uniforme.

Segunda solución: O (1) en el tiempo/ O (n) en el espacio (uniforme)

davidhigh ya se dio la solución con un vector, pero hay un problema porque cuando pop un elemento de tu pila, tendrás que realizar una búsqueda lineal en O (n) o puedes reconstruir tu vector cada vez que quieras recuperar un elemento aleatorio pero eso es O (n) también.

Para evitar este problema y mantener la inserción/eliminación de O (log n), se puede mantener un std::unordered_set y utilizar un similar method a la primera solución para conseguir un elemento aleatorio en O (1).

p.s .: Si sus elementos son grandes, puede utilizar un conjunto desordenado de punteros (con un hasher modificado) para ahorrar algo de memoria.

Answer 5

C++ 17 std::sample

Ésta será una conveniente, aunque (O) (n) el método no es muy eficiente:

#include <algorithm> 
#include <iostream> 
#include <random> 
#include <set> 
#include <vector> 

int main() { 
    std::set<int> in{1, 2, 3, 5, 7}; 
    std::vector<int> 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; 
} 

Pero creo que para la eficiencia sólo tiene que copiar a otro tipo de estructura: How to select a random element in std::set in less than O(n) time?