Prendre la n éléments aléatoires à partir d'une Liste<E>?
Comment puis-je prendre des n éléments aléatoires à partir d'une ArrayList<E>
? Idéalement, je voudrais être en mesure de faire des appels successifs à la take()
méthode pour obtenir un autre x éléments, sans remplacement.
- de quoi prendre() dans ArrayList?
- qu'avez-vous à ce jour? Si vous obtenez un autre x éléments, vous pouvez choisir les éléments à partir de la précédente série de nouveau, ou doivent être tous différents tout le temps jusqu'à ce que TOUS les éléments sont sélectionnés? (Alors, quelle est la prochaine étape?)
- Sans remplacement. Lorsque vous n'avez plus à gauche, vous devriez obtenir rien en retour.
Vous devez vous connecter pour publier un commentaire.
Deux manières principales.
Utilisation
Random#nextInt(int)
:Ce n'est pourtant pas garanti que les
n
appels retourne des éléments uniques.Utilisation
Collections#shuffle()
:Il vous permet d'obtenir
n
des éléments uniques par un indice incrémenté (en supposant que la liste elle-même contient des éléments uniques).Dans le cas où vous vous demandez si il y a un Java 8 Flux approche; non, il n'est pas intégré. Il n'y a pas une telle chose comme
Comparator#randomOrder()
dans la norme API (encore?). Vous pouvez essayer quelque chose comme ci-dessous tout en répondant à la stricteComparator
contrat (bien que la distribution est assez terrible):Mieux utiliser
Collections#shuffle()
à la place.La plupart des solutions proposées jusqu'à maintenant suggèrent soit une pleine liste de lecture aléatoire ou successives aléatoire de prélèvement par la vérification de l'unicité et recommencez si nécessaire.
Mais, nous pouvons profiter de la Durstenfeld de l'algorithme (les plus populaires de Fisher-Yates variante de nos jours).
En raison de ce qui précède, nous n'avons pas besoin de mélanger l'ensemble de la liste, mais exécuter la boucle, pour toutes les étapes du nombre d'éléments nécessaires à la déclaration. L'algorithme s'assure que les N derniers éléments à la fin de la liste est 100% aléatoire, si nous avons utilisé une parfaite fonction aléatoire.
Parmi les nombreux scénarios du monde où nous avons besoin de choisir un prédéterminé (max) montant des éléments aléatoires de tableaux/listes, cette méthode optimisée est très utile pour les différents jeux de cartes, comme le Texas Poker, où vous a-priori de connaître le nombre de cartes par jeu; seul un nombre limité de cartes est habituellement requis à partir du pont.
Si vous voulez successivement pick n les éléments de la liste et être en mesure de le faire sans remplacement de plus de et plus et plus encore une fois, vous êtes probablement mieux de hasard permutant les éléments, puis en prenant des morceaux off en blocs de n. Si vous permuter aléatoirement la liste vous garantir statistique aléatoire pour chaque bloc vous de choisir. Peut-être la façon la plus simple de le faire est d'utiliser
Collections.shuffle
.Simple et clair
arrayList
ettargetList
.Une juste façon de le faire est de parcourir la liste, sur la n-ième itération de calcul de la probabilité de savoir si ou de ne pas choisir le n-ième élément, qui est essentiellement la fraction du nombre d'éléments que vous devez toujours choisir le nombre d'éléments disponibles dans le reste de la liste. Par exemple:
(Ce code copié à partir d'une page que j'ai écrit il y a un moment sur sélection d'un échantillon aléatoire à partir d'une liste.)
Utiliser la classe suivante:
Garder la sélection d'un élément aléatoire et assurez-vous que vous ne choisissez pas le même élément nouveau:
En théorie, cela pourrait courir à l'infini, mais dans la pratique, il est très bien. Plus vous vous rapprochez de l'ensemble de la liste initiale, le ralentissement de l'exécution de la présente obtient évidemment, mais ce n'est pas le point de la sélection aléatoire d'une sous-liste, est-il?
Comme indiqué dans d'autres réponses,
Collections.shuffle
n'est pas très efficace lorsque la source de la liste est grande, en raison de la copie. Voici une Java 8 one-liner qui:Code:
Cependant, pour une liste sans rapide d'accès aléatoire (comme LinkedList) la complexité serait
n*O(list_size)
.La classe suivante récupérer les N éléments d'une liste de tout type. Si vous fournissez une graine puis à chaque exécution, il sera de retour la même liste, sinon, les éléments de la nouvelle liste change à chaque exécution. Vous pouvez le vérifier son comportement en cours d'exécution les principales méthodes.