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

 
#lang racket
 
(define (one-of-n n)
  (for/fold ([n 0]) ([i (in-range 1 n)])
    (if (zero? (random (add1 i))) i n)))
 
(define (try n times)
  (define rs (make-vector n 0))
  (for ([i (in-range times)])
    (define r (one-of-n n))
    (vector-set! rs r (add1 (vector-ref rs r))))
  (vector->list rs))
 
(define TIMES 1000000)
(for ([n (in-range 1 21)])
  (define rs (try n TIMES))
  (printf "~a: ~a\n    ~a\n" (~a #:width 2 n) rs
          (map (lambda (r) (~a (round (/ r TIMES 1/100)) "%")) rs)))
 
#| Sample Run:
 
1 : (1000000)
    (100%)
2 : (499702 500298)
    (50% 50%)
3 : (332426 333314 334260)
    (33% 33% 33%)
4 : (249925 250083 249695 250297)
    (25% 25% 25% 25%)
5 : (200304 199798 199920 199983 199995)
    (20% 20% 20% 20% 20%)
6 : (166276 167085 165955 166792 167143 166749)
    (17% 17% 17% 17% 17% 17%)
7 : (142067 143242 142749 142997 143248 142746 142951)
    (14% 14% 14% 14% 14% 14% 14%)
8 : (125026 125187 125214 124770 124785 125141 125039 124838)
    (13% 13% 13% 12% 12% 13% 13% 12%)
9 : (111551 111013 110741 111292 111105 110627 110570 111685 111416)
    (11% 11% 11% 11% 11% 11% 11% 11% 11%)
10: (100322 100031 100176 100590 99799 99892 100305 99955 99493 99437)
    (10% 10% 10% 10% 10% 10% 10% 10% 10% 10%)
11: (91237 90706 90962 90901 90872 91002 91164 90967 90092 90706 91391)
    (9% 9% 9% 9% 9% 9% 9% 9% 9% 9% 9%)
12: (83046 83556 83003 84128 83264 83305 83093 83202 83430 83605 83276 83092)
    (8% 8% 8% 8% 8% 8% 8% 8% 8% 8% 8% 8%)
13: (77282 76936 76667 76659 76771 76736 77165 77190 77341 76469 76985 76942 76857)
    (8% 8% 8% 8% 8% 8% 8% 8% 8% 8% 8% 8% 8%)
14: (71389 71496 71141 71314 71670 72062 71979 71361 71198 71457 70854 71686 71300 71093)
    (7% 7% 7% 7% 7% 7% 7% 7% 7% 7% 7% 7% 7% 7%)
15: (66534 66571 66072 66977 66803 66894 67076 66409 66306 67222 66590 66780 66341 66680 66745)
    (7% 7% 7% 7% 7% 7% 7% 7% 7% 7% 7% 7% 7% 7% 7%)
16: (62155 62496 62846 62136 62447 62714 62228 62454 62527 62577 62775 62692 62491 62231 62460 62771)
    (6% 6% 6% 6% 6% 6% 6% 6% 6% 6% 6% 6% 6% 6% 6% 6%)
17: (58852 59046 58726 58782 58979 58725 59051 58935 58910 59082 58567 58863 58625 58922 58648 58456 58831)
    (6% 6% 6% 6% 6% 6% 6% 6% 6% 6% 6% 6% 6% 6% 6% 6% 6%)
18: (55204 55683 55547 55492 55671 55467 55801 55704 55235 55411 55482 55387 55679 55557 55398 55649 55815 55818)
    (6% 6% 6% 6% 6% 6% 6% 6% 6% 6% 6% 6% 6% 6% 6% 6% 6% 6%)
19: (52564 52283 52918 52363 52316 52511 52500 53042 52594 52720 52577 52623 52762 53047 52798 52832 52267 52550 52733)
    (5% 5% 5% 5% 5% 5% 5% 5% 5% 5% 5% 5% 5% 5% 5% 5% 5% 5% 5%)
20: (50107 50008 49786 50128 50431 49905 50109 49781 50099 50117 49772 50128 49721 49937 49735 50067 49865 50155 50231 49918)
    (5% 5% 5% 5% 5% 5% 5% 5% 5% 5% 5% 5% 5% 5% 5% 5% 5% 5% 5% 5%)
 
|#
 