Reservoir Sampling

randomSample

using System;

// Given a stream of numbers, return a set of k (fixed) numbers from it uniformly at random. 
// Also, prove that your solution is actually uniformly random.- https://en.wikipedia.org/wiki/Reservoir_sampling

namespace ReservoirSampling
{
    public class Program
    {
        public static void Main(string[] args)
        {
            int[] input = new int[] {1, 2, 3, 4, 5, 6, 7, 8};
        
            StreamPicker picker = new StreamPicker(3);
        
            foreach(int item in input) {
                picker.Add(item);
            }
            
            picker.Display();
        }
    }
    
    class StreamPicker {
        
        int[] reservoir;
        int count;
        
        Random randomGenerator;
        
        int maxCapacity;
        public StreamPicker(int k) {
            reservoir = new int[k];
            count = 0;
            maxCapacity = k;
            randomGenerator = new Random();
        }
        
        public void Add(int data) {
            if (count < maxCapacity) {
                reservoir[count] = data;
            } else {
                int replacementIndex = randomGenerator.Next(count);
                if (replacementIndex < maxCapacity) {
                    reservoir[replacementIndex] = data;
                }
            }
            count++;
        }
        
        public void Display() {
            int countOfDataAvailable = Math.Min(maxCapacity, count);
                        
            for (int i = 0; i < countOfDataAvailable; i++) {
                Console.Write(reservoir[i] + " ");
            }
            Console.WriteLine();
        }
        
    }
}