जलाशय नमूनाकरण

जलाशय नमूनाकरण एक यादृच्छिक एल्गोरिथम है। इस एल्गोरिथम में, k आइटम को n अलग-अलग आइटम वाली सूची से चुना जाता है।

हम इसे k आकार के भंडार के रूप में एक सरणी बनाकर हल कर सकते हैं। फिर बेतरतीब ढंग से मुख्य सूची से एक तत्व चुनें और उस वस्तु को जलाशय सूची में रखें। जब एक आइटम को एक बार चुना जाता है, तो उसे अगली बार के लिए नहीं चुना जाएगा। लेकिन उनका तरीका कारगर नहीं है, हम इस तरीके से जटिलता को बढ़ा सकते हैं।

जलाशय सूची में, सूची से पहले k आइटम कॉपी करें, अब सूची में (k+1) वें नंबर से एक-एक करके, वर्तमान चयनित आइटम को इंडेक्स i पर रखा गया है। 0 से i तक एक यादृच्छिक सूचकांक खोजें और इसे j में संग्रहीत करें, यदि j 0 से k की सीमा में है, तो सूची [i] के साथ जलाशय [j] को स्वैप करें।

इनपुट और आउटपुट

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