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

Question

Comment choisir un élément aléatoire dans un ensemble ? Je suis particulièrement intéressé par le prélèvement d'un élément aléatoire dans un HashSet ou un LinkedHashSet, en Java. Les solutions pour d'autres langages sont également les bienvenues.

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 peu plus loin, vous savez :

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

Answer 3

Solution rapide pour Java en utilisant un ArrayList et un HashMap : [élément -> indice].

Motivation : J'avais besoin d'un ensemble d'articles avec RandomAccess notamment pour choisir un élément aléatoire dans l'ensemble (cf. pollRandom mé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();
    }
}

Answer 4

Si vous voulez le faire en Java, vous devriez envisager de copier les éléments dans une sorte de collection à accès aléatoire (telle qu'une ArrayList). Car, à moins que votre ensemble soit petit, l'accès à l'élément sélectionné sera coûteux (O(n) au lieu de O(1)). [ed : la copie de liste est aussi O(n)].

Sinon, vous pouvez chercher une autre implémentation de Set qui correspond mieux à vos besoins. Le site ListOrderedSet de Commons Collections semble prometteur.

Answer 5

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