Escogiendo un elemento aleatorio de un conjunto

¿Cómo elijo un elemento aleatorio de un conjunto? Estoy particularmente interesado en elegir un elemento aleatorio de un HashSet o un LinkedHashSet, en Java. Las soluciones para otros idiomas también son bienvenidas.

int size = myHashSet.size(); int item = new Random().nextInt(size); // In real life, the Random object should be rather more shared than this int i = 0; for(Object obj : myhashSet) { if (i == item) return obj; i++; } 

Algo relacionado Did You Know:

Hay métodos útiles en java.util.Collections para barajar colecciones enteras: Collections.shuffle(List) Y Collections.shuffle(List list, Random rnd) .

Solución rápida para Java utilizando ArrayList y HashMap : [elemento -> índice].

Motivación: necesitaba un conjunto de elementos con propiedades de pollRandom aleatorio, especialmente para elegir un elemento aleatorio del conjunto (consulte el método pollRandom ). La navegación aleatoria en un árbol binario no es precisa: los árboles no están perfectamente equilibrados, lo que no conduciría a una distribución uniforme.

 public class RandomSet extends AbstractSet { List dta = new ArrayList(); Map idx = new HashMap(); public RandomSet() { } public RandomSet(Collection items) { for (E item : items) { idx.put(item, dta.size()); dta.add(item); } } @Override public boolean add(E item) { if (idx.containsKey(item)) { return false; } idx.put(item, dta.size()); dta.add(item); return true; } /** * Override element at position id with last element. * @param id */ public E removeAt(int id) { if (id >= dta.size()) { return null; } E res = dta.get(id); idx.remove(res); E last = dta.remove(dta.size() - 1); // skip filling the hole if last is removed if (id < dta.size()) { idx.put(last, id); dta.set(id, last); } return res; } @Override public boolean remove(Object item) { @SuppressWarnings(value = "element-type-mismatch") Integer id = idx.get(item); if (id == null) { return false; } removeAt(id); return true; } public E get(int i) { return dta.get(i); } public E pollRandom(Random rnd) { if (dta.isEmpty()) { return null; } int id = rnd.nextInt(dta.size()); return removeAt(id); } @Override public int size() { return dta.size(); } @Override public Iterator iterator() { return dta.iterator(); } } 

Esto es más rápido que el ciclo for-each en la respuesta aceptada:

 int index = rand.nextInt(set.size()); Iterator iter = set.iterator(); for (int i = 0; i < index; i++) { iter.next(); } return iter.next(); 

La construcción for-each llama a Iterator.hasNext() en cada ciclo, pero desde el index < set.size() , esa verificación es una sobrecarga innecesaria. Vi un 10-20% de aumento en la velocidad, pero YMMV. (Además, esto se comstack sin tener que agregar una statement de devolución adicional).

Tenga en cuenta que este código (y la mayoría de las demás respuestas) se puede aplicar a cualquier colección, no solo a Set. En forma de método genérico:

 public static  E choice(Collection coll, Random rand) { if (coll.size() == 0) { return null; // or throw IAE, if you prefer } int index = rand.nextInt(coll.size()); if (coll instanceof List) { // optimization return ((List) coll).get(index); } else { Iterator iter = coll.iterator(); for (int i = 0; i < index; i++) { iter.next(); } return iter.next(); } } 

Si desea hacerlo en Java, debería considerar copiar los elementos en algún tipo de colección de acceso aleatorio (como ArrayList). Porque, a menos que su conjunto sea pequeño, acceder al elemento seleccionado será costoso (O (n) en lugar de O (1)). [ed: list copy también es O (n)]

Alternativamente, podría buscar otra implementación de Conjunto que se aproxime más a sus requisitos. ListOrderedSet de Commons Collections parece prometedor.

En Java:

 Set set = new LinkedHashSet(3); set.add(1); set.add(2); set.add(3); Random rand = new Random(System.currentTimeMillis()); int[] setArray = (int[]) set.toArray(); for (int i = 0; i < 10; ++i) { System.out.println(setArray[rand.nextInt(set.size())]); } 
 List asList = new ArrayList(mySet); Collections.shuffle(asList); return asList.get(0); 

Solución Clojure:

 (defn pick-random [set] (let [sq (seq set)] (nth sq (rand-int (count sq))))) 

¿No puedes obtener el tamaño / longitud del conjunto / matriz, generar un número aleatorio entre 0 y el tamaño / longitud, y luego llamar al elemento cuyo índice coincide con ese número? HashSet tiene un método .size (), estoy bastante seguro.

En psuedocode –

 function randFromSet(target){ var targetLength:uint = target.length() var randomIndex:uint = random(0,targetLength); return target[randomIndex]; } 

Perl 5

 @hash_keys = (keys %hash); $rand = int(rand(@hash_keys)); print $hash{$hash_keys[$rand]}; 

Aquí hay una manera de hacerlo.

C ++. Esto debería ser razonablemente rápido, ya que no requiere iterar sobre todo el conjunto ni clasificarlo. Esto debería funcionar de la caja con la mayoría de los comstackdores modernos, suponiendo que sean compatibles con tr1 . De lo contrario, es posible que necesite usar Boost.

Los documentos de Boost son útiles aquí para explicar esto, incluso si no usa Boost.

El truco consiste en utilizar el hecho de que los datos se han dividido en segmentos, y para identificar rápidamente un segmento elegido al azar (con la probabilidad adecuada).

 //#include  //using namespace boost; #include  using namespace std::tr1; #include  #include  #include  using namespace std; int main() { unordered_set u; u.max_load_factor(40); for (int i=0; i<40; i++) { u.insert(i); cout << ' ' << i; } cout << endl; cout << "Number of buckets: " << u.bucket_count() << endl; for(size_t b=0; b::const_local_iterator l = u.begin(b); while(x>0) { l++; assert(l!=u.end(b)); x--; } cout << "random item is " << *l << ". "; cout << endl; } } 

La solución anterior habla en términos de latencia pero no garantiza la misma probabilidad de que se seleccione cada índice.
Si eso necesita ser considerado, pruebe el muestreo de yacimientos. http://en.wikipedia.org/wiki/Reservoir_sampling .
Collections.shuffle () (como lo sugieren algunos) usa uno de esos algoritmos.

Como dijo “Las soluciones para otros idiomas también son bienvenidas”, esta es la versión para Python:

 >>> import random >>> random.choice([1,2,3,4,5,6]) 3 >>> random.choice([1,2,3,4,5,6]) 4 

PHP, suponiendo que “set” es una matriz:

 $foo = array("alpha", "bravo", "charlie"); $index = array_rand($foo); $val = $foo[$index]; 

Las funciones de Mersenne Twister son mejores, pero no hay MT equivalente de array_rand en PHP.

El icono tiene un tipo de conjunto y un operador de elemento aleatorio, unario “?”, Por lo que la expresión

 ? set( [1, 2, 3, 4, 5] ) 

producirá un número aleatorio entre 1 y 5.

La inicialización aleatoria se inicializa a 0 cuando se ejecuta un progtwig, por lo que para producir resultados diferentes en cada ejecución use al randomize()

Cª#

  Random random = new Random((int)DateTime.Now.Ticks); OrderedDictionary od = new OrderedDictionary(); od.Add("abc", 1); od.Add("def", 2); od.Add("ghi", 3); od.Add("jkl", 4); int randomIndex = random.Next(od.Count); Console.WriteLine(od[randomIndex]); // Can access via index or key value: Console.WriteLine(od[1]); Console.WriteLine(od["def"]); 

Solución de Javascript;)

 function choose (set) { return set[Math.floor(Math.random() * set.length)]; } var set = [1, 2, 3, 4], rand = choose (set); 

O alternativamente:

 Array.prototype.choose = function () { return this[Math.floor(Math.random() * this.length)]; }; [1, 2, 3, 4].choose(); 

En lisp

 (defun pick-random (set) (nth (random (length set)) set)) 

En Mathematica:

 a = {1, 2, 3, 4, 5} a[[ ⌈ Length[a] Random[] ⌉ ]] 

O, en versiones recientes, simplemente:

 RandomChoice[a] 

Esto recibió un voto negativo, tal vez porque carece de explicación, así que aquí uno es:

Random[] genera un float pseudoaleatorio entre 0 y 1. Esto se multiplica por la longitud de la lista y luego la función de techo se usa para redondear al siguiente entero. Este índice luego se extrae de a .

Como la funcionalidad de la tabla hash se realiza con frecuencia con reglas en Mathematica, y las reglas se almacenan en listas, se puede usar:

 a = {"Badger" -> 5, "Bird" -> 1, "Fox" -> 3, "Frog" -> 2, "Wolf" -> 4}; 

Esto es idéntico a la respuesta aceptada (Khoth), pero con el size innecesario y las variables i eliminadas.

  int random = new Random().nextInt(myhashSet.size()); for(Object obj : myhashSet) { if (random-- == 0) { return obj; } } 

Aunque eliminando las dos variables mencionadas anteriormente, la solución anterior sigue siendo aleatoria porque confiamos en el azar (comenzando en un índice seleccionado al azar) para decrementarse a 0 en cada iteración.

Desafortunadamente, esto no se puede hacer de manera eficiente (mejor que O (n)) en cualquiera de los contenedores del conjunto de la Biblioteca estándar.

Esto es extraño, ya que es muy fácil agregar una función de selección aleatoria a conjuntos de hash así como a conjuntos binarios. En un conjunto de hash no disperso, puedes probar entradas aleatorias, hasta que obtengas un hit. Para un árbol binario, puede elegir aleatoriamente entre el subárbol izquierdo o derecho, con un máximo de O (log2) pasos. Implementé una demostración de la siguiente a continuación:

 import random class Node: def __init__(self, object): self.object = object self.value = hash(object) self.size = 1 self.a = self.b = None class RandomSet: def __init__(self): self.top = None def add(self, object): """ Add any hashable object to the set. Notice: In this simple implementation you shouldn't add two identical items. """ new = Node(object) if not self.top: self.top = new else: self._recursiveAdd(self.top, new) def _recursiveAdd(self, top, new): top.size += 1 if new.value < top.value: if not top.a: top.a = new else: self._recursiveAdd(top.a, new) else: if not top.b: top.b = new else: self._recursiveAdd(top.b, new) def pickRandom(self): """ Pick a random item in O(log2) time. Does a maximum of O(log2) calls to random as well. """ return self._recursivePickRandom(self.top) def _recursivePickRandom(self, top): r = random.randrange(top.size) if r == 0: return top.object elif top.a and r <= top.a.size: return self._recursivePickRandom(top.a) return self._recursivePickRandom(top.b) if __name__ == '__main__': s = RandomSet() for i in [5,3,7,1,4,6,9,2,8,0]: s.add(i) dists = [0]*10 for i in xrange(10000): dists[s.pickRandom()] += 1 print dists 

Obtuve [995, 975, 971, 995, 1057, 1004, 966, 1052, 984, 1001] como salida, por lo que la distribución se ve bien.

He luchado con el mismo problema para mí, y todavía no he decidido si el clima de la ganancia de rendimiento de esta selección más eficiente vale la pena sobrecargar una colección basada en Python. Por supuesto, podría refinarlo y traducirlo a C, pero eso es demasiado trabajo para mí hoy 🙂

En Java 8:

 static  E getRandomSetElement(Set set) { return set.stream().skip(new Random().nextInt(set.size())).findFirst().orElse(null); } 

PHP, usando MT:

 $items_array = array("alpha", "bravo", "charlie"); $last_pos = count($items_array) - 1; $random_pos = mt_rand(0, $last_pos); $random_item = $items_array[$random_pos]; 

Por diversión, escribí un RandomHashSet basado en el muestreo de rechazo. Es un poco hacky, ya que HashMap no nos permite acceder a su tabla directamente, pero debería funcionar bien.

No utiliza memoria adicional, y el tiempo de búsqueda es O (1) amortizado. (Debido a que java HashTable es denso).

 class RandomHashSet extends AbstractSet { private Map map = new HashMap<>(); public boolean add(V v) { return map.put(new WrapKey(v),v) == null; } @Override public Iterator iterator() { return new Iterator() { RandKey key = new RandKey(); @Override public boolean hasNext() { return true; } @Override public V next() { while (true) { key.next(); V v = map.get(key); if (v != null) return v; } } @Override public void remove() { throw new NotImplementedException(); } }; } @Override public int size() { return map.size(); } static class WrapKey { private V v; WrapKey(V v) { this.v = v; } @Override public int hashCode() { return v.hashCode(); } @Override public boolean equals(Object o) { if (o instanceof RandKey) return true; return v.equals(o); } } static class RandKey { private Random rand = new Random(); int key = rand.nextInt(); public void next() { key = rand.nextInt(); } @Override public int hashCode() { return key; } @Override public boolean equals(Object o) { return true; } } } 

También puede transferir el conjunto a una matriz de uso de matriz; probablemente funcionará a pequeña escala, veo el ciclo for en la respuesta más votada es O (n) de todos modos

 Object[] arr = set.toArray(); int v = (int) arr[rnd.nextInt(arr.length)]; 

Si realmente quieres elegir “cualquier” objeto del Set , sin ninguna garantía sobre la aleatoriedad, lo más fácil es tomar el primero devuelto por el iterador.

  Set s = ... Iterator it = s.iterator(); if(it.hasNext()){ Integer i = it.next(); // i is a "random" object from set } 

El más fácil con Java 8 es:

 outbound.stream().skip(n % outbound.size()).findFirst().get() 

donde n es un entero aleatorio. Por supuesto, es de menos rendimiento que con el for(elem: Col)

Una solución genérica usando la respuesta de Khoth como punto de partida.

 /** * @param set a Set in which to look for a random element * @param  generic type of the Set elements * @return a random element in the Set or null if the set is empty */ public  T randomElement(Set set) { int size = set.size(); int item = random.nextInt(size); int i = 0; for (T obj : set) { if (i == item) { return obj; } i++; } return null; } 

Si el tamaño del conjunto no es grande, entonces usando matrices esto se puede hacer.

 int random; HashSet someSet; [] randData; random = new Random(System.currentTimeMillis).nextInt(someSet.size()); randData = someSet.toArray();  sResult = randData[random]; 
    Intereting Posts