Choisir un élément aléatoire à partir d'un ensemble

un peu apparenté saviez-vous:

il y a des méthodes utiles dans java.util.Collections pour mélanger des collections entières: Collections.shuffle(List<?>) et Collections.shuffle(List<?> list, Random rnd) .

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

Motivation: j'ai eu besoin d'un ensemble d'éléments avec des propriétés RandomAccess , surtout pour choisir un élément aléatoire de l'ensemble (voir pollRandom méthode). La navigation au hasard 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 pour-chaque 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();

le pour-chaque construction appelle Iterator.hasNext() sur chaque boucle, mais depuis index < set.size() , ce contrôle est inutile au-dessus. J'ai vu une augmentation de 10 à 20% de la vitesse, mais YMMV. (Aussi, cette compile sans avoir à ajouter une instruction de retour.)

notez que ce code (et la plupart des autres réponses) peut être appliqué à n'importe quelle Collection, pas seulement définie. 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 un ArrayList). Parce que, à moins que votre ensemble soit petit, accéder à l'élément sélectionné coûtera cher (O(n) au lieu de O(1)). [ed: la copie de liste est aussi O(n)]

alternativement, vous pouvez chercher une autre implémentation qui correspond mieux à vos besoins. Le ListOrderedSet des Collections communes l'air prometteur.

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

Clojure solution:

(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 assez rapide, car il ne nécessite pas d'itération sur l'ensemble, ou le tri. Cela devrait fonctionner avec la plupart des compilateurs modernes, en supposant qu'ils supportent tr1 . Sinon, vous devrez peut-être utiliser Boost.

le Boost docs 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 d'identifier rapidement un choisi au hasard seau (avec la probabilité).

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

Solution ci-dessus parler en termes de latence, mais ne garantit pas une probabilité égale de chaque indice étant sélectionné.

Si cela doit être considéré, essayez réservoir d'échantillonnage. http://en.wikipedia.org/wiki/Reservoir_sampling .

Collections.shuffle () (comme suggéré par few) utilise un tel algorithme.

puisque vous avez dit "les Solutions pour d'autres langues 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 un .méthode taille (), je suis assez sûr.

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

icône a un type d'ensemble et un opérateur d'éléments aléatoires, unary "?", ainsi 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 quand un programme est lancé, donc pour produire des résultats différents sur chaque course 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"]);

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

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, il suffit de:

RandomChoice[a]

cette proposition a reçu un vote négatif, peut-être parce qu'elle manque d'explication, donc en voici une:

Random[] génère un flotteur de pseudorandom 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 de a .

puisque la fonctionnalité de la table de hachage est souvent faite avec des règles dans Mathematica, et les règles sont stockées dans des listes, on pourrait utiliser:

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

Que Diriez-vous de juste

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

identique à la réponse acceptée (Khoth), mais sans les variables inutiles size et i .

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

bien que la suppression des deux variables susmentionnées, la solution ci-dessus reste aléatoire parce que nous comptons sur le hasard (à partir d'un indice choisi au hasard) pour se décrémenter vers 0 au cours de chaque itération.

malheureusement, cela ne peut pas être fait efficacement (mieux que O(n)) dans n'importe quel conteneur standard de la bibliothèque.

c'est étrange, car il est très facile d'ajouter une fonction de sélection aléatoire aux ensembles de hachage aussi bien que des ensembles binaires. Dans un jeu de hash non à sparse, vous pouvez essayer des entrées aléatoires, jusqu'à ce que vous obtenez un résultat. Pour un arbre binaire, vous pouvez choisir au hasard entre le sous-arbre gauche ou droit, avec un maximum de O(log2) pas. J'ai mis en place une démo de la dernière 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 [995, 975, 971, 995, 1057, 1004, 966, 1052, 984, 1001] comme la production,de sorte que les coutures de distribution bon.

je me suis battu avec le même problème pour moi-même, et je n'ai pas encore décidé si le temps le gain de performance de ce pick plus efficace vaut le coup d'utiliser une collection basée sur python. Je pourrais bien sûr le raffiner et le traduire en C, mais c'est trop de travail pour moi aujourd'hui:)

En Java 8:

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

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

pour le plaisir, J'ai écrit un RandomHashSet basé sur l'échantillonnage de rejet. C'est un peu hacky, puisque HashMap ne nous permet pas d'accéder directement à sa table, mais ça devrait très bien marcher.

il n'utilise pas de 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;
        }
    }
}

vous pouvez également transférer le jeu de tableaux utiliser le tableau il va probablement fonctionner à petite échelle je vois la boucle pour dans la réponse la plus votée est O (N) de toute façon

Object[] arr = set.toArray();

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

si vous voulez vraiment choisir" n'importe quel "objet du Set , sans aucune garantie sur le caractère aléatoire, le plus facile 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
    }

le plus facile avec Java 8 est:

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

où n est un entier aléatoire. Bien sûr, il est de moins de performance que celle avec le for(elem: Col)

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

si la taille définie n'est pas grande alors en utilisant des tableaux cela peut être fait.

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