84

からn個のランダムな要素を取得するにはどうすればよいArrayList<E>ですか? take()理想的には、メソッドを連続して呼び出して、別の x 要素を置換せずに取得できるようにしたいと考えています。

4

12 に答える 12

117

主な方法は2つ。

  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()代わりに使用することをお勧めします。

于 2011-01-15T20:49:07.820 に答える
39

これまでに提案されたソリューションのほとんどは、完全なリストのシャッフルまたは一意性をチェックすることによる連続したランダム ピッキングのいずれかを提案し、必要に応じて再試行します。

ただし、Durstenfeld のアルゴリズム (現在最も人気のある Fisher-Yates の変種) を利用することはできます。

Durstenfeld の解決策は、反復ごとに最後に打たれなかった番号と交換することによって、「打たれた」番号をリストの最後に移動することです。

上記により、リスト全体をシャッフルする必要はありませんが、返す必要がある要素の数だけループを実行します。このアルゴリズムは、完全なランダム関数を使用した場合、リストの最後の 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());
}
于 2016-02-08T20:05:51.550 に答える
10

リストから n 個の要素を連続して選択し、何度も何度も置換せずにそれを実行できるようにする場合は、要素をランダムに並べ替えてから、n 個のブロックでチャンクを削除するのがおそらく最善です。リストをランダムに並べ替えると、選択した各ブロックの統計的ランダム性が保証されます。おそらくこれを行う最も簡単な方法は、 を使用することCollections.shuffleです。

于 2011-01-15T20:46:39.333 に答える
6

これを行うための公正な方法は、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;
}

(このコードは、リストからランダムなサンプルを選択することについて少し前に書いたページからコピーしたものです。)

于 2011-01-15T22:39:54.663 に答える
2

次のクラスを使用します。

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;
    }
}
于 2015-03-20T02:32:19.497 に答える