Escogiendo un elemento aleatorio de un conjunto

Question

¿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.

Answer 1

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++; 
} 

Answer 2

ya que dijo "Soluciones para otros idiomas también son bienvenidos", aquí está la versión de Python:

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

Answer 3

En Java:

Set<Integer> set = new LinkedHashSet<Integer>(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())]); 
} 

Answer 4

no puedes obtener el tamaño/longitud del conjunto/matriz, generar un número aleatorio entre 0 y el tamaño/longitud, 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]; 
} 

Answer 5

PHP, asumiendo "set" es una matriz:

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

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

Answer 6

PHP, utilizando 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]; 

Answer 7

solución 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(); 

Answer 8

Una de alguna manera relacionado sabía usted:

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

Answer 9

Perl 5

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

Esta es una manera de hacerlo.

Answer 10

Icon tiene un tipo de conjunto y un operador-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 semilla aleatoria se inicializa a 0 cuando se ejecuta un programa, por lo que para producir diferentes resultados en cada uso de ejecución randomize()

Answer 11

En 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"]); 

Answer 12

en Lisp

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

Answer 13

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: la copia de la lista también es O (n)]

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

Answer 14

solución Clojure:

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

Answer 15

Desafortunadamente, esto no se puede hacer de manera eficiente (mejor que O (n)) en cualquiera de la librería estándar establece contenedores.

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. He implementado una demostración de la tarde 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 

llegué [995, 975, 971, 995, 1057, 1004, 966, 1052, 984, 1001] como salida, por lo que las costuras de distribución bien.

He luchado con el mismo problema para mí, y aún no he decidido si el clima el 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 :)

Answer 16

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 compiladores modernos, suponiendo que admitan tr1. De lo contrario, es posible que necesite usar Boost.

El Boost docs son útiles aquí para explicar esto, incluso si no usa Boost.

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

//#include <boost/unordered_set.hpp> 
//using namespace boost; 
#include <tr1/unordered_set> 
using namespace std::tr1; 
#include <iostream> 
#include <stdlib.h> 
#include <assert.h> 
using namespace std; 

int main() { 
    unordered_set<int> 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<u.bucket_count(); b++) 
    cout << "Bucket " << b << " has " << u.bucket_size(b) << " elements. " << endl; 

    for(size_t i=0; i<20; i++) { 
    size_t x = rand() % u.size(); 
    cout << "we'll quickly get the " << x << "th item in the unordered set. "; 
    size_t b; 
    for(b=0; b<u.bucket_count(); b++) { 
     if(x < u.bucket_size(b)) { 
     break; 
     } else 
     x -= u.bucket_size(b); 
    } 
    cout << "it'll be in the " << b << "th bucket at offset " << x << ". "; 
    unordered_set<int>::const_local_iterator l = u.begin(b); 
    while(x>0) { 
     l++; 
     assert(l!=u.end(b)); 
     x--; 
    } 
    cout << "random item is " << *l << ". "; 
    cout << endl; 
    } 
} 

Answer 17

después de leer este hilo, lo mejor que podría escribir es:

static Random random = new Random(System.currentTimeMillis()); 
public static <T> T randomChoice(T[] choices) 
{ 
    int index = random.nextInt(choices.length); 
    return choices[index]; 
} 

Answer 18

solución rápida para Java usando un ArrayList y una HashMap: [elemento -> Indice].

Motivación: Necesitaba un conjunto de elementos con propiedades RandomAccess, 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<E> extends AbstractSet<E> { 

    List<E> dta = new ArrayList<E>(); 
    Map<E, Integer> idx = new HashMap<E, Integer>(); 

    public RandomSet() { 
    } 

    public RandomSet(Collection<E> 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 <code>id</code> 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<E> iterator() { 
     return dta.iterator(); 
    } 
} 

Answer 19

En Mathematica:

a = {1, 2, 3, 4, 5} 

a[[ ⌈ Length[a] Random[] ⌉ ]] 

O, en versiones recientes, simplemente:

RandomChoice[a] 

---

Esta recibieron una baja votación, tal vez debido a que carece de explicación, asi que aquí uno es:

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

Desde funcionalidad de tabla hash se realiza con frecuencia con las normas en Mathematica, y las reglas se almacenan en listas, se podría utilizar:

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

Answer 20

List asList = new ArrayList(mySet); 
Collections.shuffle(asList); 
return asList.get(0); 

Answer 21

¿Qué tal

public static <A> A getRandomElement(Collection<A> c, Random r) { 
    return new ArrayList<A>(c).get(r.nextInt(c.size())); 
} 

Answer 22

por diversión escribió 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 ninguna memoria extra, y el tiempo de búsqueda es O (1) amortizado. (Debido a que java HashTable es denso).

class RandomHashSet<V> extends AbstractSet<V> { 
    private Map<Object,V> map = new HashMap<>(); 
    public boolean add(V v) { 
     return map.put(new WrapKey<V>(v),v) == null; 
    } 
    @Override 
    public Iterator<V> iterator() { 
     return new Iterator<V>() { 
      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<V> { 
     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; 
     } 
    } 
} 

Answer 23

Esto es más rápido que el de-cada bucle en la respuesta aceptada:

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

El para-cada constructo llama Iterator.hasNext() en cada bucle, pero desde index < set.size(), dicho control es una sobrecarga innecesaria. Vi un 10-20% de aumento en la velocidad, pero YMMV. (Además, esto compila sin tener que agregar una declaración 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> E choice(Collection<? extends E> 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<? extends E>) coll).get(index); 
    } else { 
     Iterator<? extends E> iter = coll.iterator(); 
     for (int i = 0; i < index; i++) { 
      iter.next(); 
     } 
     return iter.next(); 
    } 
} 

Answer 24

También puede transferir el conjunto de uso array matriz probablemente trabajará en pequeña escala veo el bucle en la respuesta más votada es O (n) de todos modos

Object[] arr = set.toArray(); 

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

Answer 25

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

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

Aunque la supresión de las dos variables mencionadas, la solución anterior todavía queda al azar debido a que está confiando en al azar (a partir de un índice seleccionado aleatoriamente) para disminuir sí mismo hacia 0 sobre cada iteración.

Answer 26

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, intente con el muestreo de yacimientos.http://en.wikipedia.org/wiki/Reservoir_sampling.
Collections.shuffle() (como lo sugieren algunos) usa uno de estos algoritmos.

Answer 27

Si realmente solo quiere 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<Integer> s = ... 
    Iterator<Integer> it = s.iterator(); 
    if(it.hasNext()){ 
     Integer i = it.next(); 
     // i is a "random" object from set 
    } 

Answer 28

La forma 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)

Answer 29

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

/** 
* @param set a Set in which to look for a random element 
* @param <T> generic type of the Set elements 
* @return a random element in the Set or null if the set is empty 
*/ 
public <T> T randomElement(Set<T> 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; 
} 

Answer 30

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

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

Answer 31

Con Guava podemos hacer un poco mejor que la respuesta de Khoth:

public static E random(Set<E> set) { 
    int index = random.nextInt(set.size(); 
    if (set instanceof ImmutableSet) { 
    // ImmutableSet.asList() is O(1), as is .get() on the returned list 
    return set.asList().get(index); 
    } 
    return Iterables.get(set, index); 
} 

Answer 32

Sólo quiero dejar esto aquí:

random.choice(your_set) 

no les importa la serpiente.

Answer 33

Si no te importa una biblioteca tercera parte, la biblioteca tiene un UtilsIterableUtils que tiene un método randomFrom (iterable Iterable) que se llevará a un set y devolver un elemento aleatorio de ella

Set<Object> set = new HashSet<>(); 
set.add(...); 
... 
Object random = IterableUtils.randomFrom(set); 

Se está en el Repositorio Central de Maven en:

<dependency> 
    <groupId>com.github.rkumsher</groupId> 
    <artifactId>utils</artifactId> 
    <version>1.0</version> 
</dependency>