Prendere n elementi casuali da un elenco <E>?

Question

Come posso prendere n elementi casuali da un ArrayList<E>? Idealmente, mi piacerebbe essere in grado di effettuare chiamate successive al metodo take() per ottenere altri x elementi, senza sostituzione.

Answer 1

Due modi principali.

1. Uso Random#nextInt(int):

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

   E ', tuttavia, non garantisce che i successivi n chiamate restituisce elementi unici.

2. Uso Collections#shuffle():

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

   Vi permette di ottenere n elementi unici da un indice incrementato (supponendo che l'elenco stesso contiene elementi unici).

---

Nel caso vi stiate chiedendo se c'è un approccio flusso Java 8; no, non ce n'è uno integrato. Non esiste una cosa come Comparator#randomOrder() in API standard (ancora?). Si potrebbe provare qualcosa di simile qui di seguito, pur soddisfacendo stretto Comparator contratto (anche se la distribuzione è abbastanza terribile):

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

Migliore utilizzo Collections#shuffle() invece.

Answer 2

Se si desidera selezionare n elementi dalla lista ed essere in grado di farlo senza doverli sostituire più e più volte, probabilmente è meglio permetterne gli elementi in modo casuale, quindi rimuovere blocchi in blocchi di n. Se permetti a caso la lista, garantisci casualità statistica per ogni blocco che scegli. Forse il modo più semplice per farlo sarebbe utilizzare Collections.shuffle.

Answer 3

Un modo equo per fare ciò è passare attraverso l'elenco, all'ennesimo iterazione calcolando la probabilità di scegliere o meno l'ennesimo elemento, che è essenzialmente la frazione del numero di elementi che è ancora necessario raccogliere il numero di elementi disponibili nel resto della lista. Ad esempio: (. Questo codice copiato da una pagina che ho scritto qualche tempo fa su picking a random sample from a list)

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

Answer 4

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

Answer 5

Usare la seguente classe semplice e chiara:

import java.util.Enumeration; 
import java.util.Random; 

public class RandomPermuteIterator implements Enumeration<Long> { 
    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; 
    } 
} 

Answer 6

La maggior parte delle soluzioni proposte finora suggerisce una lista completa casuale o successiva dom picking controllando l'unicità e riprovare se necessario.

Ma, possiamo sfruttare l'algoritmo di Durstenfeld (la variante più popolare di Fisher-Yates ai nostri giorni).

soluzione Durstenfeld è spostare i numeri "colpito" alla fine lista scambiando loro con l'ultimo numero unstruck ad ogni iterazione .

causa di quanto sopra, non abbiamo bisogno di mescolare l'intera lista, ma eseguire il ciclo per il maggior numero di punti pari al numero di elementi necessari per tornare. L'algoritmo garantisce che gli ultimi N elementi alla fine della lista siano casuali al 100% se usassimo una funzione casuale perfetta.

Tra i molti scenari del mondo reale in cui abbiamo bisogno di scegliere una quantità (max) predeterminata di elementi casuali da array/liste, questo metodo ottimizzato è molto utile per vari giochi di carte, come Texas Poker, dove tu- conoscere a priori il numero di carte da utilizzare per partita; Solitamente dal mazzo è richiesto solo un numero limitato di carte.

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 7

Conservare la selezione di un elemento casuale e assicurarsi che non si sceglie di nuovo lo stesso elemento:

public static <E> List<E> selectRandomElements(List<E> list, int amount) 
{ 
    // Avoid a deadlock 
    if (amount >= list.size()) 
    { 
     return list; 
    } 

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

In teoria questo potrebbe correre all'infinito, ma in pratica è bene. Più ti avvicini all'intero elenco originale, più lento è il tempo di esecuzione di questo, ma ovviamente non è questo il punto di selezionare una sottolista casuale, vero?