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

Program OneOfNLines (Output);
 
{$IFDEF FPC}
  {$MODE DELPHI}
{$ENDIF}
 
function one_of_n(n: longint): longint;
  var
    i: longint;
  begin
    one_of_n := 1;
    for i := 2 to n do
      if random < 1.0 / i then
	one_of_n := i;
  end;
 
function sum(a: array of longint): longint;
  var
    i: integer;
  begin
    Result := 0;
    for i := low(a) to high(a) do
       Result := Result + a[i];
  end;
 
const
  num_reps = 1000000;
  num_lines_in_file = 10;
 
var
  lines: array[1..num_reps] of longint;
  i: longint;
 
begin
  randomize;
  for i := 1 to num_reps do
    lines[i] := 0;
  for i := 1 to num_reps do
    inc(lines[one_of_n(num_lines_in_file)]);
  for i := 1 to num_lines_in_file do
    writeln('Number of times line ', i, ' was selected: ', lines[i]);
  writeln('Total number selected: ', sum(lines));
end.