Matrix chain multiplication: Difference between revisions

</pre>

== {{header|Racket}} ==

<lang racket>#lang racket

(define (memoize f)

(define table (make-hash))

(λ args (hash-ref! table args (thunk (apply f args)))))

(struct $ (cost expl))

(define @ vector-ref)

(define (+: #:combine [combine (thunk* #f)] . xs)

($ (apply + (map $-cost xs)) (apply combine (map $-expl xs))))

(define (min: . xs) (argmin $-cost xs))

(define (compute dims)

(define loop

(memoize

(λ (left right)

(cond

[(= 1 (- right left)) ($ 0 left)]

[else

(for/fold ([ans ($ +inf.0 #f)]) ([mid (in-range (add1 left) right)])

(min: ans (+: (loop left mid) (loop mid right)

($ (* (@ dims left) (@ dims mid) (@ dims right)) #f)

#:combine (λ (left-answer right-answer _)

(list left-answer '× right-answer)))))]))))

(loop 0 (sub1 (vector-length dims))))

(define-syntax-rule (echo <x> ...)

(begin (printf "~a: ~a\n" (~a (quote <x>) #:width 12) <x>) ...))

(define (solve input)

(match-define-values ((list ($ cost explanation)) _ time _) (time-apply compute (list input)))

(echo input time cost explanation)

(newline))

(solve #(1 5 25 30 100 70 2 1 100 250 1 1000 2))

(solve #(1000 1 500 12 1 700 2500 3 2 5 14 10))</lang>

'''Output'''

<pre>

input : #(1 5 25 30 100 70 2 1 100 250 1 1000 2)

time : 1

cost : 38120

explanation : ((((((((0 × 1) × 2) × 3) × 4) × 5) × 6) × (7 × (8 × 9))) × (10 × 11))

input : #(1000 1 500 12 1 700 2500 3 2 5 14 10)

time : 0

cost : 1773740

explanation : (0 × ((((((1 × 2) × 3) × (((4 × 5) × 6) × 7)) × 8) × 9) × 10))