Sélection d'un élément au hasard dans un ensemble

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

Solution rapide pour Java à l'aide d'un ArrayList et un HashMap: [element -> index].

Motivation: j'avais besoin d'un ensemble d'éléments avec RandomAccess propriétés, en particulier pour choisir un élément aléatoire dans l'ensemble (voir pollRandom méthode). Hasard de la navigation dans un arbre binaire n'est pas exact: les arbres ne sont pas parfaitement équilibré, ce qui ne conduirait pas à une distribution 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();
}
}

Si vous voulez le faire en Java, vous devez envisager de copier les éléments dans une sorte de random-access collection (comme une liste de tableaux). Car, à moins que votre jeu est petit, l'accès à l'élément sélectionné sera cher (O(n) au lieu de O(1)). [ed: liste de copie est également en O(n)]

Sinon, vous pourriez regarder pour un autre Jeu de mise en œuvre qui correspond le mieux à vos exigences. Le ListOrderedSet de Communes des Collections de l'air prometteur.

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

Perl 5

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

Ici est une façon de le faire.

Solution ci-dessus parlent en termes de temps de latence, mais ne garantit pas une probabilité égale de chaque index sélectionné.

Si cela doit être considéré, essayez réservoir d'échantillonnage. http://en.wikipedia.org/wiki/Reservoir_sampling.
Les Collections.shuffle() (comme suggéré par quelques-uns) utilise un algorithme de ce type.

Tu ne peux pas obtenir la taille/longueur de la série/tableau, générer un nombre aléatoire entre 0 et la taille/longueur, puis d'appeler l'élément dont l'index correspond à ce nombre? HashSet a un .méthode size (), je suis assez sûr.

Dans psuedocode -

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

Icône a un type de jeu et un random-élément opérateur unaire "?", donc l'expression

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

va produire un nombre aléatoire entre 1 et 5.

La graine aléatoire est initialisé à 0 lorsqu'un programme est exécuté, de sorte à produire des résultats différents à chaque exécution, l'utilisation randomize()

Javascript solution 😉

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

Ou alternativement:

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

Dans Mathematica:

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

Ou, dans les versions récentes, il suffit de:

RandomChoice[a]

---

Ce reçu un vote, peut-être parce qu'il manque d'explication, ici, on est à:

Random[] génère un pseudo flotter entre 0 et 1. Ce nombre est multiplié par la longueur de la liste et puis le plafond de la fonction est utilisée pour arrondir à l'entier suivant. Cet indice est ensuite extrait à partir de a.

Depuis la table de hachage de la fonctionnalité est souvent le cas avec les règles en Mathematica, et les règles sont stockées dans des listes, on peut utiliser:

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

C'est identique à accepté de répondre (Khoth), mais avec les inutiles size et i variables supprimées.

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

Si faire l'écart avec les deux variables mentionnées ci-dessus, la solution ci-dessus reste aléatoire, car nous sommes fier au hasard (à partir de un choisi au hasard index) pour décrémenter lui-même vers 0 à chaque itération.

Dans Java 8:

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

Pour le fun, j'ai écrit un RandomHashSet repose sur le rejet de l'échantillonnage. C'est un peu hacky, depuis HashMap ne nous laisse pas accéder à la table directement, mais il devrait fonctionner très bien.

Il ne pas utiliser toute la mémoire supplémentaire, et la recherche en temps est O(1) amorti. (Parce que java table de hachage est dense).

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

Si vraiment vous voulez juste de choisir "tout" objet à partir de la Set, sans aucune garantie sur le caractère aléatoire, le plus simple est de prendre le premier est retourné par l'itérateur.

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

Une solution générique à l'aide de Khoth de répondre en tant que point de départ.

/**
* @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;
}

Avec Goyave nous pouvons faire un peu mieux que Khoth réponse:

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

après la lecture de ce thread, le meilleur que j'ai pu écrire c'est:

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