A method of choosing a line randomly from a file:

 Without reading the file more than once
 When substantial parts of the file cannot be held in memory
 Without knowing how many lines are in the file
Is to:

 keep the first line of the file as a possible choice, then
 Read the second line of the file if possible and make it the possible choice if a uniform random value between zero and one is less than 1/2.
 Read the third line of the file if possible and make it the possible choice if a uniform random value between zero and one is less than 1/3.
 ...
 Read the Nth line of the file if possible and make it the possible choice if a uniform random value between zero and one is less than 1/N
 Return the computed possible choice when no further lines exist in the file.


Task

 Create a function/method/routine called one_of_n that given n, the number of actual lines in a file, follows the algorithm above to return an integer - the line number of the line chosen from the file. 
The number returned can vary, randomly, in each run.
 Use one_of_n in a simulation to find what woud be the chosen line of a 10 line file simulated 1,000,000 times.
 Print and show how many times each of the 10 lines is chosen as a rough measure of how well the algorithm works.


Note: You may choose a smaller number of repetitions if necessary, but mention this up-front.

Note: This is a specific version of a Reservoir Sampling algorithm: https://en.wikipedia.org/wiki/Reservoir_sampling

 
-module( one_of_n_lines_in_file  ).
 
-export( [one_of_n/1, task/0] ).
 
one_of_n( N ) -> loop( N, 2, random:uniform(), 1 ).
 
task() ->
	Dict = lists:foldl( fun update_counter/2,  dict:new(), lists:seq(1, 1000000) ),
	[io:fwrite("Line ~p selected: ~p~n", [X, dict:fetch(X, Dict)]) || X <- lists:sort(dict:fetch_keys(Dict))].
 
 
loop( Max, N, _Random, Acc ) when N =:= Max + 1 -> Acc;
loop( Max, N, Random, _Acc ) when Random < (1/N) -> loop( Max, N + 1, random:uniform(), N );
loop( Max, N, _Random, Acc ) -> loop( Max, N + 1, random:uniform(), Acc ).
 
update_counter( _N, Dict ) -> dict:update_counter( one_of_n(10), 1, Dict ).
 