Lấy mẫu hồ chứa

Lấy mẫu hồ chứa là một thuật toán ngẫu nhiên. Trong thuật toán này, k mục được chọn từ danh sách có n mục khác nhau.

Chúng ta có thể giải quyết nó bằng cách tạo một mảng như một vùng chứa có kích thước k. Sau đó, chọn ngẫu nhiên một phần tử từ danh sách chính và đặt mục đó vào danh sách hồ chứa. Khi một mục được chọn một lần, nó sẽ không được chọn cho lần sau. Nhưng cách làm của anh ấy không hiệu quả, chúng ta có thể tăng độ phức tạp bằng phương pháp này.

Trong danh sách hồ chứa, sao chép k mục đầu tiên từ danh sách, bây giờ từng mục một từ số thứ (k + 1) trong danh sách, để mục đã chọn hiện tại được đặt ở chỉ mục i. Tìm một chỉ mục ngẫu nhiên từ 0 đến i và lưu trữ nó vào j, nếu j nằm trong khoảng từ 0 đến k, thì hoán đổi hồ chứa [j] với danh sách [i].

Đầu vào và Đầu ra

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

Thuật toán

chooseKItems(array, n, k)

Đầu vào: Mảng, số phần tử trong mảng, số phần tử cần chọn.

Đầu ra: Chọn k phần tử một cách ngẫu nhiên.

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

Ví dụ

#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);
}

Đầu ra

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