貯水池サンプリング

サイズkのリザーバーとして配列を作成することで、これを解決できます。次に、メインリストからランダムに1つの要素を選択し、そのアイテムをリザーバーリストに配置します。一度選択した項目は、次回は選択されません。しかし、彼のアプローチは効果的ではありません。この方法で複雑さを増すことができます。

リザーバーリストで、リストから最初のk個のアイテムをコピーし、リストの（k + 1）番目の番号から1つずつコピーして、現在選択されているアイテムをインデックスiに配置します。 0からiまでのランダムなインデックスを見つけて、それをjに格納します。jが0からkの範囲にある場合は、reservoer[j]をlist[i]と交換します。

入力と出力

Input:
The list of integers: {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12}, The value of k = 6
Output:
K-Selected items in the given array: 8 2 7 9 12 6

アルゴリズム

chooseKItems(array, n, k)

入力： 配列、配列内の要素の数、選択する要素の数。

出力： k個の要素をランダムに選択します。

Begin
   define output array of size [k]
   copy k first items from array to output

   while i < n, do
      j := randomly choose one value from 0 to i
      if j < k, then
         output[j] := array[i]
      increase i by 1
   done
   display output array
End

例

#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;

void display(int array[], int n) {
   for (int i = 0; i < n; i++)
      cout << array[i] << " ";
}

void chooseKItems(int array[], int n, int k) {        //it will choose k items from the array
   int i;
   int output[k];
   for (i = 0; i < k; i++)
      output[i] = array[i];

   srand(time(NULL));        //use time function to get different seed value

   while(i < n) {
      int j = rand() % (i+1);         //random index from 0 to i

      if (j < k)          //copy ith element to jth element in the output array
         output[j] = array[i];
      i++;
   }

   cout << "K-Selected items in the given array: ";
   display(output, k);
}

int main() {
   int array[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12};
   int n = 12;
   int k = 6;
   chooseKItems(array, n, k);
}

出力

K-Selected items in the given array: 8 2 7 9 12 6