জলাধার স্যাম্পলিং

জলাধার স্যাম্পলিং হল একটি এলোমেলো অ্যালগরিদম৷ এই অ্যালগরিদমে, n ভিন্ন আইটেম সহ একটি তালিকা থেকে k আইটেম নির্বাচন করা হয়।

আমরা 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