#include <stdio.h>
#include <stdlib.h>
#include <time.h>
/*
* get_random_sample()
*
* Selects k unique random elements from an input array.
*
* Parameters:
* array - source array
* array_size - number of elements in the source array
* k - number of random elements to retrieve
* result - output array of size at least k
*
* Notes:
* - Sampling is done without replacement.
* - The original array is not modified.
* - Uses a partial Fisher-Yates shuffle, which is O(k).
*/
int get_random_sample(
const int *array,
size_t array_size,
size_t k,
int *result)
{
if (array == NULL || result == NULL) {
return -1;
}
if (k > array_size) {
return -1;
}
/*
* Create a working copy because we do not
* want to modify the caller's array.
*/
int *temp = malloc(array_size * sizeof(int));
if (temp == NULL) {
return -1;
}
for (size_t i = 0; i < array_size; ++i) {
temp[i] = array[i];
}
/*
* Partial Fisher-Yates shuffle:
*
* After each iteration, one random element
* is moved into its final position.
*
* We only perform k iterations because we
* only need k random values.
*/
for (size_t i = 0; i < k; ++i) {
size_t random_index =
i + (size_t)(rand() % (array_size - i));
int tmp = temp[i];
temp[i] = temp[random_index];
temp[random_index] = tmp;
}
for (size_t i = 0; i < k; ++i) {
result[i] = temp[i];
}
free(temp);
return 0;
}
int main(void)
{
/* Array size is known only at runtime. */
int numbers[] = {
10, 20, 30, 40, 50,
60, 70, 80, 90, 100
};
size_t array_size =
sizeof(numbers) / sizeof(numbers[0]);
size_t k = 4;
int sample[4];
/* Seed the random number generator once. */
srand((unsigned int)time(NULL));
if (get_random_sample(
numbers,
array_size,
k,
sample) != 0)
{
fprintf(stderr, "Failed to retrieve sample.\n");
return EXIT_FAILURE;
}
printf("Random sample:\n");
for (size_t i = 0; i < k; ++i) {
printf("%d ", sample[i]);
}
return EXIT_SUCCESS;
}
/*
run:
Random sample:
70 30 60 20
*/
