n 個の中から k 個を選ぶ 質問する

とO(1)ハッシュテーブル、部分フィッシャー・イェイツ法はO(け）時間と空間を節約します。秘訣は、かわったハッシュ テーブル内の配列の要素。

以下は Java での簡単な例です。

public static int[] getRandomSelection (int k, int n, Random rng) {
    if (k > n) throw new IllegalArgumentException(
        "Cannot choose " + k + " elements out of " + n + "."
    );

    HashMap<Integer, Integer> hash = new HashMap<Integer, Integer>(2*k);
    int[] output = new int[k];

    for (int i = 0; i < k; i++) {
        int j = i + rng.nextInt(n - i);
        output[i] = (hash.containsKey(j) ? hash.remove(j) : j);
        if (j > i) hash.put(j, (hash.containsKey(i) ? hash.remove(i) : i));
    }
    return output;
}