Prendre n éléments aléatoires dans une Liste<E> ?

Question

Comment prendre n éléments au hasard dans un ArrayList<E> ? Idéalement, j'aimerais pouvoir faire des appels successifs à la fonction take() pour obtenir x autres éléments, sans remplacement.

Answer 1

Comme indiqué dans d'autres réponses, Collections.shuffle n'est pas très efficace lorsque la liste des sources est grande, à cause de la copie. Voici un one-liner Java 8 qui :

• suffisamment efficace sur les listes à accès aléatoire comme ArrayList si vous n'avez pas besoin de beaucoup d'éléments de la source
• ne modifie pas la source
• NE garantit PAS l'unicité, si ce n'est pas très important pour vous. Si vous en choisissez 5 parmi une centaine, il y a de fortes chances que les éléments soient uniques.

Code :

private static <E> List<E> pickRandom(List<E> list, int n) {
  return new Random().ints(n, 0, list.size()).mapToObj(list::get).collect(Collectors.toList());
}

Toutefois, pour une liste sans accès aléatoire rapide (comme la liste de liens), la complexité serait la suivante n*O(list_size) .

Answer 2

Utilisez la classe suivante :

import java.util.Enumeration;
import java.util.Random;

public class RandomPermuteIterator implements Enumeration<Long> {
    int c = 1013904223, a = 1664525;
    long seed, N, m, next;
    boolean hasNext = true;

    public RandomPermuteIterator(long N) throws Exception {
        if (N <= 0 || N > Math.pow(2, 62)) throw new Exception("Unsupported size: " + N);
        this.N = N;
        m = (long) Math.pow(2, Math.ceil(Math.log(N) / Math.log(2)));
        next = seed = new Random().nextInt((int) Math.min(N, Integer.MAX_VALUE));
    }

    public static void main(String[] args) throws Exception {
        RandomPermuteIterator r = new RandomPermuteIterator(100);
        while (r.hasMoreElements()) System.out.print(r.nextElement() + " ");
    }

    @Override
    public boolean hasMoreElements() {
        return hasNext;
    }

    @Override
    public Long nextElement() {
        next = (a * next + c) % m;
        while (next >= N) next = (a * next + c) % m;
        if (next == seed) hasNext = false;
        return  next;
    }
}

Answer 3

Continuez à sélectionner un élément au hasard et veillez à ne pas choisir à nouveau le même élément :

public static <E> List<E> selectRandomElements(List<E> list, int amount)
{
    // Avoid a deadlock
    if (amount >= list.size())
    {
        return list;
    }

    List<E> selected = new ArrayList<>();
    Random random = new Random();
    int listSize = list.size();

    // Get a random item until we got the requested amount
    while (selected.size() < amount)
    {
        int randomIndex = random.nextInt(listSize);
        E element = list.get(randomIndex);

        if (!selected.contains(element))
        {
            selected.add(element);
        }
    }

    return selected;
}

En théorie, ce système pourrait fonctionner à l'infini, mais en pratique, il fonctionne bien. Plus vous vous rapprochez de la liste originale, plus la durée d'exécution est lente, mais ce n'est pas le but de la sélection d'une sous-liste aléatoire, n'est-ce pas ?

Answer 4

La classe suivante permet d'extraire N éléments d'une liste de n'importe quel type. Si vous fournissez une graine, elle retournera la même liste à chaque exécution, sinon, les éléments de la nouvelle liste changeront à chaque exécution. Vous pouvez vérifier son comportement en exécutant les méthodes principales.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.Random;

public class NRandomItem<T> {
    private final List<T> initialList;

    public NRandomItem(List<T> list) {
        this.initialList = list;
    }

    /**
     * Do not provide seed, if you want different items on each run.
     * 
     * @param numberOfItem
     * @return
     */
    public List<T> retrieve(int numberOfItem) {
        int seed = new Random().nextInt();
        return retrieve(seed, numberOfItem);
    }

    /**
     * The same seed will always return the same random list.
     * 
     * @param seed,
     *            the seed of random item generator.
     * @param numberOfItem,
     *            the number of items to be retrieved from the list
     * @return the list of random items
     */
    public List<T> retrieve(int seed, int numberOfItem) {
        Random rand = new Random(seed);

        Collections.shuffle(initialList, rand);
        // Create new list with the number of item size
        List<T> newList = new ArrayList<>();
        for (int i = 0; i < numberOfItem; i++) {
            newList.add(initialList.get(i));
        }
        return newList;
    }

    public static void main(String[] args) {
        List<String> l1 = Arrays.asList("Foo", "Bar", "Baz", "Qux");
        int seedValue = 10;
        NRandomItem<String> r1 = new NRandomItem<>(l1);

        System.out.println(String.format("%s", r1.retrieve(seedValue, 2)));
    }
}

Answer 5

Cette solution ne modifie pas la liste d'origine et n'augmente pas la complexité en fonction de la taille de la liste.

Pour obtenir un échantillon de 4 personnes à partir d'une liste de 7, il suffit de sélectionner un élément au hasard parmi les 7, puis un élément au hasard parmi les 6 restants, et ainsi de suite. Si nous avons déjà sélectionné les indices 4, 0, 3, nous générons ensuite un nombre aléatoire à partir de 0, 1, 2, 3, représentant respectivement les indices 1, 2, 5, 6.

static Random rand = new Random();

static <T> List<T> randomSample(List<T> list, int size) {
    List<T> sample = new ArrayList<>();

    for (int sortedSampleIndices[] = new int[size], i = 0; i < size; i++) {
        int index = rand.nextInt(list.size() - i);

        int j = 0;
        for (; j < i && index >= sortedSampleIndices[j]; j++)
            index++;
        sample.add(list.get(index));

        for (; j <= i; j++) {
            int temp = sortedSampleIndices[j];
            sortedSampleIndices[j] = index;
            index = temp;
        }
    }

    return sample;
}