Question

How to select N reservoir items randomly from an array in C++

Answer 1

#include <iostream>
#include <vector>
 
void selectReservoir(int arr[], int N, int size) {
    std::vector<int> reservoir;  
    int items = 0;
 
    srand(time(NULL));
     
    while (items < N) {
        int index = rand() % size; // index between 0 to size
        bool found = false;

        // Check if the value present in the reservoir
        for (int j = 0; j < items; j++) {
            if (reservoir[j] == arr[index]) {
                found = true;
                break;
            }
        }

        // If not present add value to the reservoir 
        if (!found) {
            reservoir.push_back(arr[index]);
            items++;
        }
    }
     
    for (auto const &val: reservoir) {
        std::cout << val << " ";
    }
}
 
int main() {
    int arr[] = { 4, 9, 14, 96, 13, 0, 3, 99, 19, 2, 80, 1, 7 };
     
    int N = 5;
    int size = sizeof(arr) / sizeof(arr[0]);
     
    selectReservoir(arr, N, size);
}
 
  
  
/*
run:
  
19 14 13 3 80 
  
*/

 

70+ SQL courses for beginners and professionals

Answer 2

#include <iostream>
#include <vector>

std::vector<int> selectReservoir(int arr[], int N, int size) {
    std::vector<int> reservoir;  
    int items = 0;

    srand(time(NULL));
    
    while (items < N) {
        int index = rand() % size; // index between 0 to size
        bool found = false;

        // Check if the value present in the reservoir
        for (int j = 0; j < items; j++) {
            if (reservoir[j] == arr[index]) {
                found = true;
                break;
            }
        }

        // If not present add value to the reservoir 
        if (!found) {
            reservoir.push_back(arr[index]);
            items++;
        }
    }
    
    return reservoir;
}

int main() {
    int arr[] = { 4, 9, 14, 96, 13, 0, 3, 99, 19, 2, 80, 1, 7 };
    
    int N = 5;
    int size = sizeof(arr) / sizeof(arr[0]);
    
    std::vector<int> reservoir = selectReservoir(arr, N, size);
    
    for (auto const &val: reservoir) {
        std::cout << val << " ";
    }
}

 
 
/*
run:
 
0 2 96 9 80 
 
*/

 

70+ SQL courses for beginners and professionals