java - numero - Escogiendo un elemento aleatorio de un conjunto

metodo random java

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

¿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];
}

Answer 2

¿Qué tal solo

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

Answer 3

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

Answer 4

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 sean compatibles con tr1 . De lo contrario, es posible que necesite usar Boost.

Los boost.org/doc/libs/1_43_0/doc/html/unordered/buckets.html 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 <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 5

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

Answer 6

Con Guava podemos hacerlo 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 7

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 :)

Answer 8

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)

Answer 9

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

Answer 10

En lisp

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

Answer 11

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.

Answer 12

Esto es más rápido que el ciclo for-each 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();

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 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 13

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.

Answer 14

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.

Answer 15

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];

Answer 16

Perl 5

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

Aquí hay una manera de hacerlo.

Answer 17

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<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 18

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.

Answer 19

Si el tamaño del conjunto no es grande, entonces usando 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 20

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

Answer 21

Solución Clojure:

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

Answer 22

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();

Answer 23

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<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 24

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

Answer 25

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 <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 26

Icon 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 programa, por lo que para producir resultados diferentes en cada ejecución use al randomize()

Answer 27

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 28

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 29

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

Answer 30

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