Elegir 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.También se aceptan soluciones para otros idiomas.

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

Un ¿Sabías que algo relacionado?

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

Answer 3

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

Motivación:Necesitaba un conjunto de artículos con RandomAccess propiedades, especialmente para elegir un elemento aleatorio del conjunto (ver pollRandom método).La navegación aleatoria en un árbol binario no es precisa:Los árboles no están perfectamente equilibrados, lo que no daría lugar 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 4

Esto es más rápido que el bucle 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 para cada llamada Iterator.hasNext() en cada bucle, pero desde index < set.size(), ese control es un gasto innecesario.Vi un aumento de velocidad del 10 al 20%, 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 otras respuestas) se puede aplicar a cualquier Colección, no solo a Conjunto.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 5

Si desea hacerlo en Java, debería considerar copiar los elementos en algún tipo de colección de acceso aleatorio (como un 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)]

Alternativamente, puede buscar otra implementación de Set que se ajuste más a sus requisitos.El ListaOrdenadoConjunto de Commons Collections parece prometedor.

Answer 6

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 7

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

Answer 8

Solución de cloro:

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

Answer 9

perla 5

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

Aquí tienes una forma de hacerlo.

Answer 10

C++.Esto debería ser razonablemente rápido, ya que no requiere iterar sobre todo el conjunto ni ordenarlo.Esto debería funcionar de inmediato con la mayoría de los compiladores modernos, suponiendo que admitan tr1.De lo contrario, es posible que necesite utilizar Boost.

El Impulsar documentos son útiles aquí para explicar esto, incluso si no usas Boost.

El truco consiste en aprovechar el hecho de que los datos se han dividido en depósitos e identificar rápidamente un depósito 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 11

La solución anterior habla en términos de latencia, pero no garantiza la misma probabilidad de seleccionar cada índice.
Si es necesario considerar eso, intente con el muestreo del yacimiento. http://en.wikipedia.org/wiki/Reservoir_sampling.
Collections.shuffle() (como lo sugieren algunos) utiliza uno de esos algoritmos.

Answer 12

Como dijiste "Las soluciones para otros lenguajes también son bienvenidas", aquí tienes 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 13

¿No puedes simplemente 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 pseudocódigo -

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

Answer 14

PHP, asumiendo 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 existe un equivalente MT de array_rand en PHP.

Answer 15

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 semilla aleatoria se inicializa a 0 cuando se ejecuta un programa, por lo que para producir resultados diferentes en cada ejecución, utilice randomize()

Answer 16

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 17

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 18

en ceceo

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

Answer 19

En Matemáticas:

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í está:

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

Dado que la funcionalidad de la tabla hash se realiza frecuentemente con reglas en Mathematica y las reglas se almacenan en listas, se podría usar:

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

Answer 20

¿Qué tal simplemente

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

Answer 21

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

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

Aunque eliminamos las dos variables antes mencionadas, la solución anterior sigue siendo aleatoria porque confiamos en el azar (comenzando en un índice seleccionado al azar) para disminuir hacia 0 sobre cada iteración.

Answer 22

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

Esto es extraño, ya que es muy fácil agregar una función de selección aleatoria a conjuntos hash y a conjuntos binarios.En un conjunto de hash no muy escaso, puedes probar entradas aleatorias hasta que consigas un resultado.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 lo 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 resultado, por lo que la distribución parece buena.

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

Answer 23

En Java 8:

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

Answer 24

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 25

Por diversión, escribí un RandomHashSet basado en el muestreo de rechazo.Es un poco complicado, 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 se amortiza O(1).(Porque 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 26

También puede transferir el conjunto a la matriz de uso de la matriz, probablemente funcionará a pequeña escala. Veo que el bucle 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 27

Si realmente sólo quieres elegir "cualquier" objeto del Set, sin ninguna garantía de 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

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

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

dónde n es un número entero aleatorio.Por supuesto, tiene menos rendimiento que con el for(elem: Col)

Answer 29

Una solución genérica que utiliza 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 establecido no es grande, esto se puede hacer mediante el uso de matrices.

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