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

Il y a deux moyens principaux.

1. Utilisation Random#nextInt(int) :

   List<Foo> list = createItSomehow();
   Random random = new Random();
   Foo foo = list.get(random.nextInt(list.size()));

   Il n'est toutefois pas garanti que les n renvoie des éléments uniques.

2. Utilisation Collections#shuffle() :

   List<Foo> list = createItSomehow();
   Collections.shuffle(list);
   Foo foo = list.get(0);

   Il vous permet d'obtenir n les éléments uniques par un index incrémenté (en supposant que la liste elle-même contienne des éléments uniques).

---

Au cas où vous vous demanderiez s'il existe une approche Java 8 Stream, non, il n'y en a pas d'intégrée. Il n'existe pas d'approche de type Comparator#randomOrder() dans l'API standard (pour l'instant ?). Vous pourriez essayer quelque chose comme ce qui suit, tout en satisfaisant aux exigences strictes de l'API. Comparator (bien que la distribution soit assez mauvaise) :

List<Foo> list = createItSomehow();
int random = new Random().nextInt();
Foo foo = list.stream().sorted(Comparator.comparingInt(o -> System.identityHashCode(o) ^ random)).findFirst().get();

Meilleure utilisation Collections#shuffle() au lieu de cela.

Answer 2

La plupart des solutions proposées jusqu'à présent suggèrent soit un brassage complet de la liste, soit une sélection aléatoire successive en vérifiant l'unicité et en réessayant si nécessaire.

Mais nous pouvons tirer parti de l'algorithme de Durstenfeld (la variante de Fisher-Yates la plus populaire de nos jours).

La solution de Durstenfeld consiste à déplacer les numéros "frappés" vers la fin de la liste en les intervertissant avec le dernier numéro de la liste. de la liste en les échangeant avec le dernier numéro non frappé à chaque itération.

En raison de ce qui précède, nous n'avons pas besoin de mélanger toute la liste mais en exécutant la boucle pendant autant d'étapes que le nombre d'éléments requis pour le retour. L'algorithme garantit que les N derniers éléments à la fin de la liste sont 100 % aléatoires si nous utilisions une fonction aléatoire parfaite.

Parmi les nombreux scénarios réels dans lesquels il est nécessaire de sélectionner un nombre prédéterminé (maximum) d'éléments aléatoires dans des tableaux/listes, cette méthode optimisée est très utile pour divers jeux de cartes, tels que le Texas Poker, où l'on connaît a-priori le nombre de cartes à utiliser par partie ; seul un nombre limité de cartes est généralement requis à partir du jeu de cartes.

public static <E> List<E> pickNRandomElements(List<E> list, int n, Random r) {
    int length = list.size();

    if (length < n) return null;

    //We don't need to shuffle the whole list
    for (int i = length - 1; i >= length - n; --i)
    {
        Collections.swap(list, i , r.nextInt(i + 1));
    }
    return list.subList(length - n, length);
}

public static <E> List<E> pickNRandomElements(List<E> list, int n) {
    return pickNRandomElements(list, n, ThreadLocalRandom.current());
}

Answer 3

Si vous voulez choisir successivement n éléments de la liste et être en mesure de le faire sans remplacement, encore et encore et encore, il est probablement préférable de permuter aléatoirement les éléments, puis d'en prélever des morceaux par blocs de n. Si vous permutez aléatoirement la liste, vous garantissez le caractère statistiquement aléatoire de chaque bloc que vous prélevez. La façon la plus simple d'y parvenir est peut-être d'utiliser la méthode Collections.shuffle .

Answer 4

Une bonne façon de procéder consiste à parcourir la liste et à calculer, à la nième itération, la probabilité de choisir ou non le nième élément, qui est essentiellement la fraction du nombre d'éléments qu'il vous reste à choisir par rapport au nombre d'éléments disponibles dans le reste de la liste. En voici un exemple :

public static <T> T[] pickSample(T[] population, int nSamplesNeeded, Random r) {
  T[] ret = (T[]) Array.newInstance(population.getClass().getComponentType(),
                                    nSamplesNeeded);
  int nPicked = 0, i = 0, nLeft = population.length;
  while (nSamplesNeeded > 0) {
    int rand = r.nextInt(nLeft);
    if (rand < nSamplesNeeded) {
      ret[nPicked++] = population[i];
      nSamplesNeeded--;
    }
    nLeft--;
    i++;
  }
  return ret;
}

(Ce code a été copié à partir d'une page que j'ai écrite il y a quelque temps sur les choisir un échantillon aléatoire dans une liste .)

Answer 5

Simple et clair

   // define ArrayList to hold Integer objects
    ArrayList<Integer> arrayList = new ArrayList<>();

    for (int i = 0; i < maxRange; i++) {
        arrayList.add(i + 1);
    }

    // shuffle list
    Collections.shuffle(arrayList);

    // adding defined amount of numbers to target list
    ArrayList<Integer> targetList = new ArrayList<>();
    for (int j = 0; j < amount; j++) {
        targetList.add(arrayList.get(j)); 
    }

    return targetList;