リストからnランダムな要素を取ります？
https://stackoverflow.com/questions/4702036
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian質問
anからnランダムな要素を採取するにはどうすればよいですか ArrayList<E>？理想的には、私は連続して電話をかけたいと思っています take() 交換せずに別のX要素を取得する方法。
解決
2つの主な方法。
使用する
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ストリームアプローチがあるかどうか疑問に思っている場合。いいえ、組み込みのものはありません。そのようなものはありません 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() 代わりは。
他のヒント
提案されているソリューションのほとんどは、これまでのところ、完全なリストシャッフルまたは一意性をチェックし、必要に応じて再試行することにより、連続したランダムピッキングのいずれかを提案しています。
しかし、Durstenfeldのアルゴリズム（私たちの時代で最も人気のある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());
}
リストからn要素を連続的に選択し、何度も何度も交換せずにそれを行うことができる場合は、おそらく要素にランダムに順応し、nのブロックでチャンクを外すのが最善です。リストにランダムに並べ替えると、選択する各ブロックの統計的ランダム性を保証します。おそらくこれを行う最も簡単な方法は、使用することです Collections.shuffle.
シンプルで明確です
// 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;
これを行うための公正な方法は、NTH要素を選択するかどうかの確率を計算する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;
}
（このコードは、私がしばらく前に書いたページからコピーしました リストからランダムサンプルを選択します.)
次のクラスを使用します。
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;
}
}
ランダムな要素を選択し続け、同じ要素を再度選択しないようにしてください。
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;
}
理論的には、これは際限なく実行される可能性がありますが、実際には問題ありません。オリジナルリスト全体を近づけるほど、これのランタイムは明らかに遅くなりますが、それはランダムなサブリストを選択するポイントではありませんか？
他の答えに記載されているように、 Collections.shuffle コピーのため、ソースリストが大きい場合、それほど効率的ではありません。これがJava 8ワンライナーです：
- ソースから多くの要素を必要としない場合、アレイリストのようなランダムアクセスリストで十分に効率的です
- ソースを変更しません
- それがあなたにとって非常に重要ではないなら、一意性を保証するものではありません。 100から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).
次のクラスは、あらゆるタイプのリストから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)));
}
}
