[your code here]

a a at a.com
Fri Feb 17 23:33:45 PST 2012



> Assuming that by "any" you mean "any particular", you would 
> have to read all the lines first. Otherwise, if the code 
> selects the first line with probability 1/K, then I can just 
> input some other number of lines.

I'm not sure if I understood your post correctly, but it seems to 
me that you didn't read the code carefully. The code selects the 
last read line with probability 1/n, where n is the number of 
strings already read, not the number of all strings. Say you have 
have already read n strings and they are all selected with 
probability 1/n. Now you read a new string and select it with 
probability  1 / (n+1). The probability that you didn't select 
the new string is then n / (n + 1) and the first n strings are 
selected with probability 1 / n * n / (n + 1) = 1 / (n + 1), so 
you now have n+1 lines all selected with probability 1 / (n + 1). 
So if the property that input strings are all selected with equal 
probability holds for n, it must also hold for n+1. Since it 
obviously holds for n = 1 (we just select the only string with 
probability 1 in that case), it must hold for all n.



More information about the Digitalmars-d mailing list