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

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; Нет, нет встроенного. Нет такой вещи, как 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

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

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

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

Из -за вышеизложенного, Нам не нужно перетасовать весь список, но запустите петлю столько шагов, сколько и количества элементов, необходимых для возврата. Алгоритм гарантирует, что последние 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 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

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

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 7

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

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