Memoizing count-combinations

count-combinations.clj

;; gorilla-repl.fileformat = 1

;; @@
(ns count-combinations)
;; @@
;; =>
;;; {"type":"html","content":"<span class='clj-nil'>nil</span>","value":"nil"}
;; <=

;; **
;;; This is your implementation of count-combinations:
;; **

;; @@
(defn count-combinations [total denom]
  (cond (= total 0) 1
        (or (< total 0) (empty? denom)) 0
        :else (+ (count-combinations total (rest denom))
                 (count-combinations (- total (first denom)) denom))))
;; @@
;; =>
;;; {"type":"html","content":"<span class='clj-var'>#&#x27;count-combinations/count-combinations</span>","value":"#'count-combinations/count-combinations"}
;; <=

;; **
;;; It's slow for large totals.
;; **

;; @@
(count-combinations 1324 [1 5 10 25])
;; @@
;; =>
;;; {"type":"html","content":"<span class='clj-long'>322578</span>","value":"322578"}
;; <=

;; @@
(time (count-combinations 1324 [1 5 10 25]))
;; @@
;; ->
;;; &quot;Elapsed time: 8310.394583 msecs&quot;
;;; 
;; <-
;; =>
;;; {"type":"html","content":"<span class='clj-long'>322578</span>","value":"322578"}
;; <=

;; **
;;; We can speed it up with memoization.  First, we need to tell Clojure this is a dynamic var.  Other than the addition of `^:dynamic`, this is exactly your code.
;; **

;; @@
(defn ^:dynamic count-combinations [total denom]
  (cond (= total 0) 1
        (or (< total 0) (empty? denom)) 0
        :else (+ (count-combinations total (rest denom))
                 (count-combinations (- total (first denom)) denom))))
;; @@
;; =>
;;; {"type":"html","content":"<span class='clj-var'>#&#x27;count-combinations/count-combinations</span>","value":"#'count-combinations/count-combinations"}
;; <=

;; **
;;; Now we can write the faster version as a memoization wrapper around your implementation.
;; **

;; @@
(defn count-combinations-fast [total denom]
  (binding [count-combinations (memoize count-combinations)]
    (last (for [i (range (inc total))]
            (count-combinations i denom)))))
;; @@
;; =>
;;; {"type":"html","content":"<span class='clj-var'>#&#x27;count-combinations/count-combinations-fast</span>","value":"#'count-combinations/count-combinations-fast"}
;; <=

;; @@
(time (count-combinations-fast 1324 [1 5 10 25]))
;; @@
;; ->
;;; &quot;Elapsed time: 23.5844 msecs&quot;
;;; 
;; <-
;; =>
;;; {"type":"html","content":"<span class='clj-long'>322578</span>","value":"322578"}
;; <=

;; @@

;; @@