Взять 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 Stream; нет, встроенного нет. В стандартном API нет такой вещи, как Comparator#randomOrder() (пока?). Вы могли бы попробовать что-то вроде ниже, все еще удовлетворяя строгому 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

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

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

Решение Дюрстенфельда состоит в том, чтобы переместить «пораженные» числа в конец списка, поменяв их местами с последним нерушаемым числом на каждой итерации.

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

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

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 3

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

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

Справедливый способ сделать это - просмотреть список на n-й итерации, рассчитав вероятность того, выбрать или не выбрать n-й элемент, который, по сути, представляет собой долю от числа элементов, которые вам все еще нужно выбрать над количество элементов, доступных в остальной части списка. Например:

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 6

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

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

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

Answer 7

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

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 8

Как отмечалось в других ответах, Collections.shuffle не очень эффективен, когда большой список источников, из-за копирования. Вот одна строка Java 8, которая:

• достаточно эффективен в списках произвольного доступа, таких как ArrayList, если вам не нужно много элементов из источника
• не изменяет источник
• НЕ гарантирует уникальность, если это не супер важно для вас. Если вы выберете 5 из ста, очень вероятно, что элементы будут уникальными.

Код:

private static <E> List<E> pickRandom(List<E> list, int n) {
  return new Random().ints(n, 0, list.size()).mapToObj(list::get).collect(Collectors.toList());
}

Однако для списка без быстрого произвольного доступа (например, LinkedList) сложность будет n*O(list_size).

Answer 9

Следующий класс извлекает N элементов из списка любого типа. Если вы предоставите начальное значение, то при каждом запуске он будет возвращать один и тот же список, в противном случае элементы нового списка будут меняться при каждом запуске. Вы можете проверить его поведение, выполнив основные методы.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.Random;

public class NRandomItem<T> {
    private final List<T> initialList;

    public NRandomItem(List<T> list) {
        this.initialList = list;
    }

    /**
     * Do not provide seed, if you want different items on each run.
     * 
     * @param numberOfItem
     * @return
     */
    public List<T> 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<T> retrieve(int seed, int numberOfItem) {
        Random rand = new Random(seed);

        Collections.shuffle(initialList, rand);
        // Create new list with the number of item size
        List<T> newList = new ArrayList<>();
        for (int i = 0; i < numberOfItem; i++) {
            newList.add(initialList.get(i));
        }
        return newList;
    }

    public static void main(String[] args) {
        List<String> l1 = Arrays.asList("Foo", "Bar", "Baz", "Qux");
        int seedValue = 10;
        NRandomItem<String> r1 = new NRandomItem<>(l1);

        System.out.println(String.format("%s", r1.retrieve(seedValue, 2)));
    }
}