Racket random list-ref function

Question

Определите функцию, которая принимает непустой список и возвращает элемент списка, выбранный случайным образом и с равной вероятностью. (Не используйте встроенную процедуру списка-ref.)

Я застрял на этом. Я чувствую, что вам нужно будет подсчитать, сколько раз функция запускается рекурсивно и сравнивает ее со случайным числом, которое вы получаете, но я не знаю, как это сделать в BSL +. Любая помощь будет действительно велика.

Answer 1

Здесь является решением. Чтобы получить мяч, первый элемент списка выбирается в качестве кандидата для возврата. Затем для каждого элемента остальных элементов в списке мы произвольно выбираем, следует ли заменить кандидата.

Например: для списка с двумя элементами '(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 теории, этот тип алгоритма принадлежит «алгоритмов выборки».

Answer 2

Я беру комментарий о том, что не использую list-ref как направление, чтобы думать о проблеме рекурсивно.

Предположение о том, что «равная вероятность» не учитывает недостатки наивных программных RNG.

Обратите внимание, что мы используем []-notation в определении функции, чтобы сказать, что шаги, если не указано иное, будет иметь значение (по умолчанию) из (random (длина 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