Reservoir Sampling | GeeksforGeeks

Reservoir sampling is a family of randomized algorithms for randomly choosing k samples from a list of n items, where n is either a very large or unknown number. 
It can be solved in O(n) time. The solution also suits well for input in the form of stream. The idea is similar to this post. Following are the steps.
1) Create an array reservoir[0..k-1] and copy first k items of stream[] to it.
2) Now one by one consider all items from (k+1)th item to nth item.
…a) Generate a random number from 0 to i where i is index of current item in stream[]. Let the generated random number is j.
…b) If j is in range 0 to k-1, replace reservoir[j] with arr[i]

void selectKItems(int stream[], int n, int k)

{

    int i;  // index for elements in stream[]

 

    // reservoir[] is the output array. Initialize it with

    // first k elements from stream[]

    int reservoir[k];

    for (i = 0; i < k; i++)

        reservoir[i] = stream[i];

 

    // Use a different seed value so that we don't get

    // same result each time we run this program

    srand(time(NULL));

 

    // Iterate from the (k+1)th element to nth element

    for (; i < n; i++)

    {

        // Pick a random index from 0 to i.

        int j = rand() % (i+1);

 

        // If the randomly  picked index is smaller than k, then replace

        // the element present at the index with new element from stream

        if (j < k)

          reservoir[j] = stream[i];

    }

 

    printf("Following are k randomly selected items \n");

    printArray(reservoir, k);

}

Read full article from Reservoir Sampling | GeeksforGeeks