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

Un poco relacionado ¿Sabía usted:

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

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

Motivación: necesitaba un conjunto de elementos con RandomAccesspropiedades, especialmente para elegir un elemento aleatorio del conjunto (ver pollRandommétodo). 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();
    }
}

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 Iterator.hasNext()a cada ciclo, pero desde entonces index < set.size(), esa verificación es una sobrecarga innecesaria. Vi un aumento del 10-20% 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 otras respuestas) se pueden aplicar a cualquier Colección, no solo a Establecer. 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();
    }
}

Si desea hacerlo en Java, debería considerar copiar los elementos en algún tipo de colección de acceso aleatorio (como una 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 coincida más estrechamente con sus requisitos. El ListOrderedSet de Commons Collections parece prometedor.

En Java 8:

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

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

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

Esto es idéntico a la respuesta aceptada (Khoth), pero con lo innecesario sizey las ivariables 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 aleatoria (comenzando en un índice seleccionado aleatoriamente) para disminuir hacia 0cada iteración.

Solución Clojure:

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

Perl 5

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

Aquí hay una forma de hacerlo.

C ++. Esto debería ser razonablemente rápido, ya que no requiere iterar en todo el conjunto u ordenarlo. Esto debería funcionar de inmediato con la mayoría de los compiladores modernos, suponiendo que sean compatibles con tr1 . Si no, es posible que deba usar Boost.

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

El truco consiste en hacer uso del hecho de que los datos se han dividido en cubos e identificar rápidamente un cubo 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;
  }
}

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 sugieren algunos) usa uno de esos algoritmos.

Como dijiste "Las soluciones para otros idiomas también son bienvenidas", aquí está 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

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

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 un equivalente MT 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 programa, por lo que para producir resultados diferentes en cada ejecución, use 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 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í hay uno:

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 se extrae de a.

Dado que la funcionalidad de la tabla hash se realiza con frecuencia 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};

¿Qué tal solo

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

Por diversión, escribí un RandomHashSet basado en muestras 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. (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;
        }
    }
}

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

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

donde nes un entero aleatorio. Por supuesto, es de menor rendimiento que eso con elfor(elem: Col)

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

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

también puede transferir el conjunto a la matriz usar 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)];

Si realmente solo desea 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
    }

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

Desafortunadamente, esto no se puede hacer de manera eficiente (mejor que O (n)) en ninguno de los contenedores de conjuntos 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 y conjuntos binarios. En un conjunto de hash no escaso, puede intentar entradas aleatorias, hasta que obtenga un acierto. 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 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 salida, por lo que la distribución parece buena.

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