Tome n elementos aleatorios de una lista ?

¿Cómo puedo tomar n elementos aleatorios de una ArrayList ? Idealmente, me gustaría poder hacer llamadas sucesivas al método take() para obtener otros x elementos, sin reemplazo.

Dos formas principales.

  1. Use Random#nextInt(int) :

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

    Sin embargo, no se garantiza que las n llamadas sucesivas devuelvan elementos únicos.

  2. Usar Collections#shuffle() :

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

    Le permite obtener n elementos únicos mediante un índice incrementado (suponiendo que la lista misma contenga elementos únicos).


En caso de que se pregunte si hay un enfoque Java 8 Stream; no, no hay uno incorporado. No existe el Comparator#randomOrder() en la API estándar (¿todavía?). Podrías probar algo como lo que se muestra a continuación sin dejar de cumplir el estricto contrato de Comparator (aunque la distribución es bastante terrible):

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

Mejor use Collections#shuffle() lugar.

La mayoría de las soluciones propuestas hasta ahora sugieren una lista completa aleatoria o una selección aleatoria sucesiva al verificar la exclusividad y volver a intentarlo si es necesario.

Pero podemos aprovechar el algoritmo de Durstenfeld (la variante Fisher-Yates más popular en nuestros días).

La solución de Durstenfeld es mover los números “golpeados” al final de la lista intercambiándolos con el último número sin tocar en cada iteración.

Debido a lo anterior, no es necesario barajar toda la lista , sino ejecutar el ciclo para obtener tantos pasos como la cantidad de elementos necesarios para devolver. El algoritmo asegura que los últimos N elementos al final de la lista son 100% aleatorios si utilizamos una función aleatoria perfecta.

Entre los muchos escenarios del mundo real donde tenemos que elegir una cantidad predeterminada (máxima) de elementos aleatorios de matrices / listas, este método optimizado es muy útil para varios juegos de cartas, como Texas Poker, donde a priori conoce el número de cartas que se utilizarán por juego; solo se requiere un número limitado de cartas del mazo.

 public static  List pickNRandomElements(List 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  List pickNRandomElements(List list, int n) { return pickNRandomElements(list, n, ThreadLocalRandom.current()); } 

Si desea elegir sucesivamente n elementos de la lista y puede hacerlo sin reemplazo una y otra vez, probablemente sea mejor permutar aleatoriamente los elementos, y luego eliminar fragmentos en bloques de n. Si permutas aleatoriamente la lista, garantizas la aleatoriedad estadística para cada bloque que elijas. Quizás la forma más fácil de hacer esto sería usar Collections.shuffle .

Simple y claro

  // define ArrayList to hold Integer objects ArrayList 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 targetList = new ArrayList<>(); for (int j = 0; j < amount; j++) { targetList.add(arrayList.get(j)); } return targetList; 

Una manera justa de hacer esto es revisar la lista, en la enésima iteración, calculando la probabilidad de elegir o no el elemento n-ésimo, que es esencialmente la fracción de la cantidad de elementos que aún debe elegir sobre la cantidad de elementos disponible en el rest de la lista. Por ejemplo:

 public static  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; } 

(Este código fue copiado de una página que escribí hace un tiempo para elegir una muestra aleatoria de una lista ).

Use la siguiente clase:

 import java.util.Enumeration; import java.util.Random; public class RandomPermuteIterator implements Enumeration { 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; } } 

Sigue seleccionando un elemento aleatorio y asegúrate de no volver a elegir el mismo elemento:

 public static  List selectRandomElements(List list, int amount) { // Avoid a deadlock if (amount >= list.size()) { return list; } List 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 teoría, esto podría funcionar interminablemente, pero en la práctica está bien. Cuanto más cerca se encuentre la lista original, más lento será el tiempo de ejecución, pero ese no es el punto de seleccionar una sublista aleatoria, ¿o sí?

La siguiente clase recupera N elementos de una lista de cualquier tipo. Si proporciona una semilla, en cada ejecución devolverá la misma lista; de lo contrario, los elementos de la nueva lista cambiarán en cada ejecución. Puedes verificar su comportamiento al ejecutar los métodos principales.

 import java.util.ArrayList; import java.util.Arrays; import java.util.Collections; import java.util.List; import java.util.Random; public class NRandomItem { private final List initialList; public NRandomItem(List list) { this.initialList = list; } /** * Do not provide seed, if you want different items on each run. * * @param numberOfItem * @return */ public List 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 retrieve(int seed, int numberOfItem) { Random rand = new Random(seed); Collections.shuffle(initialList, rand); // Create new list with the number of item size List newList = new ArrayList<>(); for (int i = 0; i < numberOfItem; i++) { newList.add(initialList.get(i)); } return newList; } public static void main(String[] args) { List l1 = Arrays.asList("Foo", "Bar", "Baz", "Qux"); int seedValue = 10; NRandomItem r1 = new NRandomItem<>(l1); System.out.println(String.format("%s", r1.retrieve(seedValue, 2))); } }