random_data_sampling.h

#ifndef CPP_ALGORITHM_RANDOM_DATA_SAMPLING_H
#define CPP_ALGORITHM_RANDOM_DATA_SAMPLING_H

#include <vector>

namespace RandomDataSampling
{
    /**
     * \brief Select the k elements randomly from the array with uniform probability.
     * Let A be an array with n distinct elements. Design an algorithm to return a random subset of k elements from A, where every subset has an equal chance of being chosen.
     * \param k sample size
     * \param arr input array
     * \return result array
     */
    auto OfflineRandomSampling(int k, std::vector<int>& arr) -> std::vector<int>;

    /**
     * \brief Select the k elements randomly from the array with uniform probability.
     * Design an algorithm that reads data and creates a random subset of size k, where each item has an equal chance of being included.
     * \param begin begin iterator
     * \param end end iterator
     * \param k sample size
     * \return result array
     */
    auto OnlineRandomSampling(std::vector<int>::const_iterator begin,
                              std::vector<int>::const_iterator end,
                              int k)
        -> std::vector<int>;

    /**
     * \brief Compute permutation of the array generated by random sampling.
     * \param n sample size
     * \return result array
     */
    auto ComputeRandomPermutation(int n) -> std::vector<int>;
}

#endif