储层采样

水库采样是一种随机算法。在该算法中，从具有n个不同项的列表中选择k个项。

我们可以通过创建一个数组作为大小为k的容器来解决它。然后从主列表中随机选择一个元素，然后将该项目放置在容器列表中。一次选择一项时，下次将不再选择。但是他的方法无效，我们可以通过这种方法增加复杂性。

在存储库列表中，复制列表中的前k个项目，现在从列表中的第（k + 1）个数字开始一个接一个地复制，让当前选定的项目位于索引i处。找到一个从0到i的随机索引，并将其存储到j中，如果j在0到k的范围内，则将库[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