ReservoirSampling.cs

using System;

namespace AlgorithmsAndDataStructures.Algorithms.Sampling;

public class ReservoirSampling
{
#pragma warning disable CA1822 // Mark members as static
    public int[] GetReservoirSample(SampleSource population, int sampleSize)
#pragma warning restore CA1822 // Mark members as static
    {
        if (population is null) return Array.Empty<int>();

        var reservoir = new int[sampleSize];
        var random = new Random();

        // We populate all samples from population to result right-away because we don't know whether we get sampleSize + 1 at any time at all.
        for (var i = 0; i < sampleSize; i++) reservoir[i] = population.GetNext();

        var currentPopulationSize = sampleSize;
        var nextSample = population.GetNext();

        while (nextSample > 0)
        {
            currentPopulationSize++;
            var probabilityToPickNextSample = random.Next(1, currentPopulationSize);

            if (probabilityToPickNextSample <= sampleSize) reservoir[probabilityToPickNextSample - 1] = nextSample;

            nextSample = population.GetNext();
        }

        return reservoir;
    }
}