random select

random select
 
problem:
select m number from 0 - (n-1) randomly,
 
------
solution 1
 
for each number in 0 - (n-1), in increasing order, generate a random number x, using "(x%remain) < to_select"to decide will the number be choose,
until m number is choosen,
 
time:
o(n), when n is small, this is quick, but when n is very big, this will be very slow,
 
------
solution 2
 
use set to store choosen number, until enough,
 
time:
o(m*log(m))
space:
o(m)
 
disadvangate:
when n & m is quite closer, and n is big, this might be slow,
when m is big, will need a lot memory,
 
------
solution 3
 
init a n length array in increasing order,
mix the order of first m elements in original array,
then sort the first m elements,
then use the first m elements,
 
time:
o(n+m*log(m))
 
space:
o(n)
 
------
solution 4
 
base on solution 3,
don't init a n length array, only use a map to store first 5 m elements, and the elements that has been choose for swap with,
 
time:
o(m*log(m))
 
space:
o(m)
 
------
reverse select
 
if m*2 > n, we can choose to select n-m elements, and exclude them, the remain is m elements,
 
------
code:
 
 

/* @authur [email protected] */
/**
 * problem:
 	select m number from 0 - (n-1) randomly,
 */ 
#include <stdio.h>
#include <stdlib.h>
/**
 * solution 1:
	for each number in 0 - (n-1), in increasing order, generate a random number x, 
	using "(x%remain) < to_select" to decide will the number be choose,until m number is choosen,
 * time:
 	O(n), when n is small, this is quick, but when n is very big, this will be very slow,
 */ 
void random_m_n(const int m, const int n) {
	int remain = n,to_select = m,i=0;
	while(to_select>0) {
		if(rand()%remain<to_select) {
			printf("%d,",i);
			to_select--;
		}
		remain--;
		i++;
	}
	printf("
");
}
/**
 * swap 2 int value,by pointer,
 */
void swap(int *a,int *b) {
	int c = *a; 
	*a = *b; 
	*b = c;
}
/**
 * compare function for int
 */
int int_cmp(int *a,int *b) {
	return *a-*b;
}
/**
 * solution 2:
	init a n length array in increasing order,
	mix the order of first m elements in original array,
	then sort the first m elements,
	then use the first m elements,
 * time:
	o(n+m*log(m))
 * space:
 	o(n)
 */
void random_m_n_2(const int m, const int n) {
	int arr[n],i,swp,x;
	for(i=0;i<n;i++) {
		arr[i] = i;
	}
	for(i=0;i<m;i++) {
		x = rand()%n;
		swap(arr+i,arr+x);
	}
	qsort(arr,m,4,int_cmp);
	for(i=0;i<m;i++) {
		printf("%d,",arr[i]);
	}
	printf("
");
}
int main(){
	random_m_n(30,2000);
	random_m_n(0,0);
	random_m_n(20,20);

	random_m_n_2(30,2000);
	random_m_n_2(0,0);
	random_m_n_2(20,20);
}

 
 
------