Pegue n elementos randoms de uma lista ?

Como posso pegar n elementos randoms de um ArrayList ? Idealmente, gostaria de poder fazer chamadas sucessivas ao método take() para obter outros elementos x, sem substituição.

Duas maneiras principais.

  1. Use Random#nextInt(int) :

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

    No entanto, não é garantido que n chamadas sucessivas retornem elementos exclusivos.

  2. Use Collections#shuffle() :

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

    Ele permite que você obtenha n elementos únicos por um índice incrementado (supondo que a própria lista contenha elementos exclusivos).


Caso você esteja se perguntando se há uma abordagem do Java 8 Stream; não, não há um embutido. Não existe algo como Comparator#randomOrder() na API padrão (ainda?). Você poderia tentar algo como abaixo, enquanto ainda satisfazendo o estrito contrato do Comparator (embora a distribuição seja bastante terrível):

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

Melhor usar Collections#shuffle() vez disso.

A maioria das soluções propostas até agora sugere um shuffle de lista completa ou um picking random sucessivo verificando a exclusividade e tente novamente, se necessário.

Mas, podemos aproveitar o algoritmo de Durstenfeld (a variante mais popular de Fisher-Yates em nossos dias).

A solução de Durstenfeld é mover os números “atingidos” para o final da lista, trocando-os pelo último número não ligado em cada iteração.

Devido ao acima, não precisamos embaralhar toda a lista , mas executamos o loop por tantas etapas quanto o número de elementos necessários para retornar. O algoritmo garante que os últimos N elementos no final da lista sejam 100% randoms se usarmos uma function aleatória perfeita.

Entre os muitos cenários do mundo real em que precisamos escolher uma quantidade predeterminada (max) de elementos randoms de matrizes / listas, esse método otimizado é muito útil para vários jogos de cartas, como o Texas Poker, onde você conhece a priori o número de cartas a serem usadas por jogo; apenas um número limitado de cartas é normalmente exigido do baralho.

 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()); } 

Se você quiser escolher sucessivamente n elementos da lista e conseguir fazer isso sem precisar substituí-los repetidas vezes, provavelmente será melhor alternar aleatoriamente os elementos e, em seguida, retirar blocos em blocos de n. Se você permutar aleatoriamente a lista, você garante a aleatoriedade estatística para cada bloco escolhido. Talvez a maneira mais fácil de fazer isso seja usar o Collections.shuffle .

Simples e 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; 

Uma maneira justa de fazer isso é percorrer a lista, na enésima iteração, calculando a probabilidade de escolher ou não o enésimo elemento, que é essencialmente a fração do número de itens que você ainda precisa selecionar o número de elementos. disponível no resto da lista. Por exemplo:

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

(Esse código copiado de uma página que escrevi há pouco tempo sobre a escolha de uma amostra aleatória de uma lista .)

Use a seguinte class:

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

Continue selecionando um elemento random e certifique-se de não escolher o mesmo elemento novamente:

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

Em teoria, isso poderia acontecer sem fim, mas na prática tudo bem. Quanto mais perto você fica de toda a lista original, mais lento o tempo de execução é óbvio, mas isso não é o ponto de selecionar uma sub-lista aleatória, é?

A class a seguir recupera N itens de uma lista de qualquer tipo. Se você fornecer uma semente, então, em cada execução, ela retornará a mesma lista, caso contrário, os itens da nova lista serão alterados em cada execução. Você pode verificar o comportamento dele executando os principais methods.

 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))); } } 
Intereting Posts