Average loop length

func find_loop(n) {
    var seen = Hash()
    loop {
        with (irand(1, n)) { |r|
            seen.has(r) ? (return seen.len) : (seen{r} = true)
        }
    }
}

print " N    empiric      theoric      (error)\n";
print "===  =========  ============  =========\n";

define MAX    = 20
define TRIALS = 1000

for n in (1..MAX) {
    var empiric = (1..TRIALS -> sum { find_loop(n) } / TRIALS)
    var theoric = (1..n -> sum {|k| prod(n - k + 1 .. n) * k**2 / n**(k+1) })

    printf("%3d  %9.4f  %12.4f   (%5.2f%%)\n",
        n, empiric, theoric, 100*(empiric-theoric)/theoric)
}

Output:

PreviousAudio frequency generatorNextAverages

Last updated

Was this helpful?