机架随机列表引用功能

Question

定义一个函数，该函数接受一个非空列表，并以相等的概率返回随机选择的列表元素。（不要使用内置的列表引用程序。）

我陷入了困境。我觉得你需要计算函数递归运行的次数，并将其与你得到的随机数进行比较，但我不知道如何在BSL+中做到这一点。任何帮助都会非常好。

Answer 1

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

例如：对于首先包含两个元素"（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)))]))

如果你想在谷歌上搜索理论，这种类型的算法属于"采样算法"。

Answer 2

我把关于不使用列表引用的评论作为递归思考问题的方向。

假设"等概率"没有考虑到天真的基于软件的RNG的缺陷。

请注意，我们在函数定义中使用[]-表示法表示，除非指定，否则步骤的（默认）值为（随机（长度lst））。这意味着它最初将在列表中有随机数量的"步骤"。

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

由于步骤是内部指定的（如（sub1步骤），从步骤中减去一），它将始终具有显式值，除非函数是这样应用的：

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