Choisir un élément aléatoire dans un ensemble

Comment choisir un élément aléatoire dans un ensemble? Je suis particulièrement intéressé par la sélection d'un élément aléatoire à partir d'un HashSet ou d'un LinkedHashSet, en Java. Les solutions pour d'autres langues sont également les bienvenues.

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 peu lié Le saviez-vous:

Il existe des méthodes utiles java.util.Collectionspour mélanger des collections entières: Collections.shuffle(List<?>)et Collections.shuffle(List<?> list, Random rnd).

Solution rapide pour Java utilisant un ArrayListet unHashMap : [élément -> index].

Motivation: j'avais besoin d'un ensemble d'éléments avec des RandomAccesspropriétés, en particulier pour choisir un élément aléatoire dans l'ensemble (voir pollRandomméthode). La navigation aléatoire dans un arbre binaire n'est pas précise: les arbres ne sont pas parfaitement équilibrés, 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();
    }
}

C'est plus rapide que la boucle for-each dans la réponse acceptée:

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

La construction for-each appelle Iterator.hasNext()sur chaque boucle, mais depuisindex < set.size() , cette vérification est inutile. J'ai vu une augmentation de 10 à 20% de la vitesse, mais YMMV. (De plus, cela se compile sans avoir à ajouter une instruction return supplémentaire.)

Notez que ce code (et la plupart des autres réponses) peut être appliqué à n'importe quelle collection, pas seulement à Set. Sous forme de méthode générique:

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 vous voulez le faire en Java, vous devriez envisager de copier les éléments dans une sorte de collection à accès aléatoire (comme une ArrayList). Car, à moins que votre ensemble ne soit petit, l'accès à l'élément sélectionné sera coûteux (O (n) au lieu de O (1)). [ed: la copie de la liste est également O (n)]

Vous pouvez également rechercher une autre implémentation Set qui correspond plus étroitement à vos besoins. Le ListOrderedSet de Commons Collections semble prometteur.

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

Ceci est identique à la réponse acceptée (Khoth), mais avec les variables inutiles sizeet isupprimées.

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

Bien que supprimant les deux variables susmentionnées, la solution ci-dessus reste toujours aléatoire car nous nous appuyons sur l'aléatoire (en commençant à un index choisi au hasard) pour se décrémenter à 0chaque itération.

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

Voici une façon de le faire.

C ++. Cela devrait être raisonnablement rapide, car il ne nécessite pas d'itération sur l'ensemble complet, ni de tri. Cela devrait fonctionner directement avec la plupart des compilateurs modernes, en supposant qu'ils prennent en charge tr1 . Sinon, vous devrez peut-être utiliser Boost.

Les documents Boost sont utiles ici pour expliquer cela, même si vous n'utilisez pas Boost.

L'astuce consiste à utiliser le fait que les données ont été divisées en seaux et à identifier rapidement un seau choisi au hasard (avec la probabilité appropriée).

//#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 solution ci-dessus parle en termes de latence mais ne garantit pas une probabilité égale de chaque index sélectionné.
Si cela doit être pris en compte, essayez l'échantillonnage du réservoir. http://en.wikipedia.org/wiki/Reservoir_sampling .
Collections.shuffle () (comme certains l'ont suggéré) utilise un tel algorithme.

Puisque vous avez dit "Les solutions pour d'autres langages sont également les bienvenues", voici la version pour Python:

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

Ne pouvez-vous pas simplement obtenir la taille / longueur de l'ensemble / tableau, générer un nombre aléatoire entre 0 et la taille / longueur, puis appeler l'élément dont l'index correspond à ce nombre? HashSet a une méthode .size (), j'en suis presque sûr.

Dans psuedocode -

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

PHP, en supposant que "set" est un tableau:

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

Les fonctions Mersenne Twister sont meilleures mais il n'y a pas d'équivalent MT de array_rand en PHP.

L'icône a un type d'ensemble et un opérateur d'élément aléatoire, unaire "?", Donc l'expression

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

produira un nombre aléatoire entre 1 et 5.

La graine aléatoire est initialisée à 0 lorsqu'un programme est exécuté, donc pour produire des résultats différents à chaque exécution, utilisez randomize()

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

Solution Javascript;)

function choose (set) {
    return set[Math.floor(Math.random() * set.length)];
}

var set  = [1, 2, 3, 4], rand = choose (set);

Ou bien:

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

[1, 2, 3, 4].choose();

Dans lisp

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

Dans Mathematica:

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

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

Ou, dans les versions récentes, simplement:

RandomChoice[a]

Cela a reçu un vote défavorable, peut-être parce qu'il manque d'explication, alors en voici une:

Random[]génère un flottant pseudo-aléatoire entre 0 et 1. Celui-ci est multiplié par la longueur de la liste, puis la fonction de plafond est utilisée pour arrondir au nombre entier suivant. Cet index est ensuite extrait de a.

Étant donné que la fonctionnalité de table de hachage est souvent effectuée avec des règles dans Mathematica et que les règles sont stockées dans des listes, on peut utiliser:

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

Que diriez-vous juste

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

Pour le plaisir, j'ai écrit un RandomHashSet basé sur un échantillonnage de rejet. C'est un peu piraté, car HashMap ne nous permet pas d'accéder directement à sa table, mais cela devrait fonctionner très bien.

Il n'utilise aucune mémoire supplémentaire et le temps de recherche est O (1) amorti. (Parce que java HashTable 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;
        }
    }
}

Le plus simple avec Java 8 est:

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

où nest un entier aléatoire. Bien sûr, il est moins performant que celui avec lefor(elem: Col)

Avec Guava, nous pouvons faire un peu mieux que la réponse 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, en utilisant 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];

vous pouvez également transférer l'ensemble vers un tableau d'utilisation du tableau, il fonctionnera probablement à petite échelle.Je vois de toute façon la boucle for dans la réponse la plus votée est O (n)

Object[] arr = set.toArray();

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

Si vous voulez vraiment juste choisir "n'importe quel" objet dans le Set, sans aucune garantie sur le caractère aléatoire, le plus simple est de prendre le premier 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 utilisant la réponse de Khoth comme 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;
}

Malheureusement, cela ne peut pas être fait efficacement (mieux que O (n)) dans l'un des conteneurs d'ensemble de la bibliothèque standard.

C'est étrange, car il est très facile d'ajouter une fonction de sélection aléatoire aux ensembles de hachage ainsi qu'aux ensembles binaires. Dans un ensemble de hachage pas trop clairsemé, vous pouvez essayer des entrées aléatoires, jusqu'à ce que vous obteniez un résultat. Pour un arbre binaire, vous pouvez choisir aléatoirement entre le sous-arbre gauche ou droit, avec un maximum de O (log2) étapes. J'ai implémenté une démo de ce qui suit ci-dessous:

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

J'ai eu [995, 975, 971, 995, 1057, 1004, 966, 1052, 984, 1001] comme sortie, donc la distribution semble bonne.

J'ai lutté avec le même problème pour moi-même, et je n'ai pas encore décidé que le gain de performances de ce choix plus efficace vaut la peine d'utiliser une collection basée sur python. Je pourrais bien sûr l'affiner et le traduire en C, mais c'est trop de travail pour moi aujourd'hui :)