Reservoir Sampling | GeeksforGeeks

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