Подтвердить что ты не робот

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

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

4b9b3361

Ответ 1

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

  • Используйте Random#nextInt(int):

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

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

  • Используйте 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() вместо этого.

Ответ 2

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

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

Решение 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());
}

Ответ 3

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

Ответ 4

Справедливый способ сделать это - пройти через список, на 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;
}

(Этот код скопирован со страницы, которую я написал некоторое время назад на выбор случайной выборки из списка.)

Ответ 5

Простой и понятный

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

Ответ 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;
    }
}

Ответ 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;
}

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