球拍随机列表参考函数

Question

Define a function that takes a non-empty list and returns an element of the list selected at random and with equal probability. (Do not use the built-in list-ref procedure.)

我卡在这上面了。我觉得您需要递归地计算函数运行的次数，并将其与您获得的随机数进行比较，但我不知道如何在 BSL+ 中执行此操作。任何帮助都会很棒。

Answer 1

我把关于不使用 list-ref 的评论作为递归思考问题的方向。

假设 'equal probability' 没有考虑到基于软件的原始 RNG 的缺陷。

注意我们使用[]-notation in the function definition to say that steps, unless specified, will have a (default) value of (random(长度lst))。这意味着它最初将有一个随机数量的 'steps into' 列表。

#lang racket

(define (random-element lst [steps (random (length lst))])
  (if (= steps 0)
      (first lst)
      (random-element (rest lst)
                      (sub1 steps))))

由于步骤是内部指定的（如 （子 1 步），从步骤中减去一个）它将始终具有明确的值，除非像这样应用函数：

(random-element '(42 1337 128 256))
; 256

Answer 2

这是一个解决方案。为了让球滚动，列表的第一个元素被选为要返回的候选者。然后对于列表中剩余元素的每个元素，我们随机选择是否替换候选。

例如：对于包含两个元素 '(a b) 的列表，首先选择元素 'a。 a 硬币被翻转：有 50% 的概率 'b 被返回。

检查代码以了解该算法如何适用于更大的列表：

(define (pick-random xs)
  (pick-random/helper (rest xs) (first xs) 1))

(define (pick-random/helper xs chosen k)
  (cond
    [(empty? xs) chosen]
    [else  ; with probability 1/(k+1) choose the first element of xs
     (if (= (random (+ k 1)) 0)
         (pick-random/helper (rest xs) (first xs) (+ k 1))
         (pick-random/helper (rest xs) chosen     (+ k 1)))]))

如果要google理论，这类算法属于"sampling algorithms"。

球拍随机列表参考函数

Racket random list-ref function

scheme

racket