On 11/26/2020 11:22 PM, Tim Meehan wrote:
I was trying to turn one of Knuth's random number sampling without
replacement algorithms. It seems to be working, but when it comes time
to return my prize ... nothing :(
I thought that since I was returning from inside of the named let,
that I'd get back my collection of numbers sampled without replacement.
;; algorithm taken from:
;;
https://stackoverflow.com/questions/311703/algorithm-for-sampling-without-replacement
<https://stackoverflow.com/questions/311703/algorithm-for-sampling-without-replacement>
(define (sample-without-replacement n N)
(let loop ([num-seen 0]
[num-stored 0]
[result '()])
(let ([u (random)])
(display (format "~a\n" result))
(unless (>= num-stored n)
(if (>= (* u (- N num-seen)) (- n num-stored))
(loop (add1 num-seen) num-stored result)
(loop (add1 num-seen) (add1 num-stored) (cons num-seen result))))
result)))
How to explain this ...
The problem is that 'unless' does not end the function - the calls to
'loop' are *not* in tail position, so although you are recursing, you
are not tail-recursing. Your code doesn't exit at the bottom but rather
unwinds the call stack, returning from 'loop' and and evaluating
'result' every time. At the top level, 'result' is the empty list
(passed as the argument) and that is what is being returned.
Contrast with:
(if (>= num-stored n)
result
(if (>= (* u (- N num-seen)) (- n num-stored))
(loop (add1 num-seen) num-stored result)
(loop (add1 num-seen) (add1 num-stored) (cons num-seen
result))))
When you have this kind of multiple test logic, 'cond' is your friend:
(cond
((>= num-stored n)
result)
((>= (* u (- N num-seen)) (- n num-stored))
(loop (add1 num-seen) num-stored result))
(else
(loop (add1 num-seen) (add1 num-stored) (cons num-seen result))))
Hope this helps,
George
--
You received this message because you are subscribed to the Google Groups "Racket
Users" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to racket-users+unsubscr...@googlegroups.com.
To view this discussion on the web visit
https://groups.google.com/d/msgid/racket-users/4e21e51e-0d8e-8b76-8422-7b88d3972415%40comcast.net.
