Random

C Library random function: rand() output is a 15-bit random number

int bigrand() // a 30 bits random variable
{
return RAND_MAX * rand() + rand();
}

return a random number from the range l to u

int rand(int l, int u)
{
return l + bigrand() % (u-l+1);
}

---------------------------

select with probability 2/5

bigrand() % 5 <>;

select m out of n number:

select = m
remaining = n
for i = [0, n)
******if (bigrand() % remaining ) < select
***********print i
***********select--
******remaining--

Q: Write m sorted integers random from 0...n-1

Solution-1: randomly select one number from 0 to n-1 for m times, and then sort this m element array.

Solution-2: "Shuffle card".

for i = [0, n-1)
{
swap(i, randint(i, n-1));
}



Q: read a text file and output each line randomly on the fly

always select the first line, select the second line with probability one half, the third line with probability one third and so on.