/* Return a pseudo-random integer in the range from min to max, inclusive. */
int RandomInt(int min, int max) {
	return (rand() % (max-min+1)) + min;
}

/* Return true with probability 1/n. */
bool OneInN(int n)
{
	if(n == 1)
		return true;
	return (RandomInt(0, n-1) == 0);
}

/* Struct to represent linked list. */
struct node
{
	int val;
	node* next;
};

/* Fill result with evenly-distributed values from list.
 * If n is the number of elements in list, and k is lengthResult (i.e., the number of elements in result),
 * then each of the (n P k) permutations of k elements from list are equally likely. */
void KRandomElements(int* result, int lengthResult, node* list)
{
	node* curr = list;
	int n = 1; //number of elements seen so far
	while(curr != NULL) {
		int toAdd = curr->val; //try to add next value to result
		for(int i = 0; i < lengthResult && i < n; ++i) {
			int toReplace = result[i]; //value to possibly replace
			bool replaceQ = OneInN(n-i);
			if(replaceQ) {
				result[i] = toAdd;
				toAdd = toReplace; //try to add replaced value to later entries in list
			}
		}
		curr = curr->next;
		n++;
	}
}