Как я могу взять n случайных элементов из ArrayList<E>
? В идеале я хотел бы сделать последовательные вызовы методу take()
для получения других элементов x без замены.
Возьмите n случайных элементов из списка <E>?
Ответ 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;
}
В теории это может продолжаться бесконечно, но на практике это нормально. Чем ближе вы получаете весь исходный список, тем медленнее время выполнения этого становится очевидным, но это не вопрос выбора случайного подсписок, не так ли?