Возьмите n случайных элементов из списка <E>?

Question

Как я могу взять n случайных элементов из ArrayList<E>? В идеале я хотел бы сделать последовательные вызовы метода take() для получения других элементов x без замены.

Answer 1

Два основных способа.

1. Использование Random#nextInt(int):

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

   Это, однако, не гарантирует, что последовательные вызовы n возвращает уникальные элементы.

2. Использование Collections#shuffle():

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

   Это позволяет получить n уникальные элементы от увеличивающегося индекса (при условии, что сам список содержит уникальные элементы).

---

В случае, если вам интересно, если есть поток подход Java 8; нет, нет встроенного. Нет такой вещи, как Comparator#randomOrder() в стандартном API (пока?). Вы могли бы попробовать что-то, как показано ниже, при этом отвечая строгим Comparator контракт (хотя распределение довольно ужасно):

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

Лучше использования Collections#shuffle() вместо этого.

Answer 2

Если вы хотите последовательно выбрать n элементов из списка и быть в состоянии сделать это без замены снова и снова, вы, вероятно, лучше всего произвольно переставляете элементы, а затем снимаете куски в блоках n. Если вы произвольно переставляете список, вы гарантируете статистическую случайность для каждого выбранного вами блока. Возможно, самый простой способ сделать это - использовать Collections.shuffle.

Answer 3

Справедливый способ сделать это - пройти через список, на n-й итерации, рассчитывая вероятность того, следует ли выбрать n-й элемент, который по существу является долей числа элементов, которые вам еще нужно выбрать количество элементов, доступных в остальной части списка. Например: (. Этот код скопирован со страницы я написал некоторое время назад на 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

Используйте следующий класс:

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

Большинство предлагаемых решений до сих пор предлагают либо полный перетасовать список, либо последовательно выбирая дом, проверяя уникальность и, если потребуется, повторите попытку.

Но мы можем воспользоваться алгоритмом Дурстенфельда (самым популярным вариантом Fisher-Yates в наши дни).

решения Durstenfeld является переместить «поразивший» номер до конца списка путем замены их с последним незатронутым номером на каждой итерации .

В связи с вышеизложенным, нам не нужно перетасовать весь список, но запустить цикл на столько шагов, как количество элементов, необходимых для возврата. Алгоритм гарантирует, что последние N элементов в конце списка на 100% случайны, если мы используем совершенную случайную функцию.

Среди многих сценариев реального мира, где нам нужно выбрать предопределенное (максимальное) количество случайных элементов из массивов/списков, этот оптимизированный метод очень полезен для различных карточных игр, таких как Texas Poker, где вы, априори знать количество карт, которые будут использоваться за игру; из колоды обычно требуется ограниченное количество карточек.

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

Keep выбрать случайный элемент и убедитесь, что вы не выбрали один и тот же элемент снова:

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

В теории это может работать бесконечно, но на практике это прекрасно. Чем ближе вы получаете весь исходный список, тем медленнее время выполнения этого становится очевидным, но это не вопрос выбора случайного подсписка, не так ли?