(in-package :cl-user)
;;; What is the probability that throwing an n-sided die m times
;;; will result in a sum larger/smaller than a given value?
(defparameter *sides* 8)
(defparameter *throws* 19)
(defparameter *threshold* (* 19 5))
(defparameter *largerp* t)
(defun dice (n k)
"Generates all possibilities of K throws that sum above/below N.
Two series that are permutations of each other are treated as one.
The throws are returned as increasing sequences."
(let ((fn (if *largerp* #'< #'>)))
(labels ((rec (n k min)
(if (zerop k)
(if (funcall fn n 0) '(()) '())
(iter (for i from min to *sides*)
(appending
(mapcar (lambda (lst) (cons i lst))
(rec (- n i) (1- k) i)))))))
(rec n k 1))))
(defun permutations (lst)
"Computes the permutation with repetitions according to LST,
e.g. for (1 2 2 3 5 5 5) it is 7! / (1! * 2! * 1! * 3!).
Assumes that the numbers in the list are sorted."
(labels ((rec (lst last n)
(cond ((null lst) (factorial n))
((= (car lst) last)
(rec (cdr lst) last (1+ n)))
(t (* (factorial n)
(rec (cdr lst) (car lst) 1))))))
(/ (factorial (length lst))
(rec lst 0 0))))
#| Example:
(defparameter *dice* (dice *threshold* *throws*))
(defparameter *sum* (reduce #'+ (mapcar #'permutations *dice*)))
(format t "~,2f%~%" (* 100 (/ *sum* (expt *sides* *throws*))))
=> 15.96%
|#