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

Toutes ces réponses nécessitent une liste modifiable ou se heurtent à des problèmes de performance.

Voici un extrait rapide qui nécessite O(k) d'espace supplémentaire, qui est garanti en O(k) de temps et qui n'a pas besoin d'un tableau modifiable. (Effectue des mélanges dans une carte)

  func getRandomElementsFrom(array: [Int], count: Int = 8) -> [Int] {
    if array.count <= count {
        return array
    }

    var mapper = [Int: Int]()
    var results = [Int]()

    for i in 0..<count {
        let randomIndex = Int.random(in: 0..<array.count - i)

        if let existing = mapper[randomIndex] {
            results.append(array[existing])
        } else {
            let element = array[randomIndex]
            results.append(element)
        }

        let targetIndex = array.count - 1 - i
        mapper[randomIndex] = mapper[targetIndex] ?? targetIndex 
    }

    return results
}

Answer 2

La méthode suivante renvoie un nouveau Liste d'éléments aléatoires Min(n, list.size()) extraites de la liste des paramètres. N'oubliez pas que la liste est modifiée après chaque appel. Par conséquent, chaque appel "consommera" la liste originale qui sera renvoyée. n des éléments aléatoires :

public static <T> List<T> nextRandomN(List<T> list, int n) {
  return Stream
    .generate(() -> list.remove((int) (list.size() * Math.random())))
    .limit(Math.min(list.size(), n))
    .collect(Collectors.toList());
}

Exemple d'utilisation :

List<Integer> list = new ArrayList<>(Arrays.asList(1, 2, 3, 4, 5, 6, 7, 8, 9, 10));

System.out.println(nextRandomN(list, 3).toString());
System.out.println(nextRandomN(list, 3).toString());
System.out.println(nextRandomN(list, 3).toString());
System.out.println(nextRandomN(list, 3).toString());

Exemple de sortie :

[8, 2, 3]
[4, 10, 7]
[1, 5, 9]
[6]