scheme calculating combination nCk using memoization

0
votes

I am trying to calculate how combination nCk using memoization in racket/scheme

I can't use separate recursive method to calculate n!. I have done this far, but saying this is bad syntex i actually fixed bad syntex error! but still gets an error in (let ([ans (assoc (x y) memo part!. anyone know what i have done wrong?

 (define combm
  (letrec ([memo null]
           [f (lambda (x y)
                (let ([ans (assoc (x y) memo)])
                  (if ans
                      (cdr ans)
                      (let ([new-ans (letrec ([fac (lambda (x)
                                      (if (eq? x 0)
                                          1
                                          (* x (fac (- x 1)))))])
                        (/ (fac x) (* (fac y) (fac (- x y)))))])
                        (begin
                          (set! memo (cons (cons (x y) new-ans) memo))
                          new-ans)))))])
    f))

                                     `
2
schemelispracket

2 Answers

1
votes

This expression (assoc (x y) memo) is the cause of the arror.

If you apply combm as in (combm 42 43) then (assoc (x y) memo) becomes (assoc (42 43) memo). And the (42 43) means "apply the value 42 on 43". The problem is that 42 is not a function.

Try (assoc (list x y) memo) instead.

0
votes

Here is a possible solution, which memoizes the factorial function:

(define combm
  (let ((memo '()))
    (lambda (n r)
      (letrec ((fact (lambda (n)
                       (let ((ans (assoc n memo =)))
                         (if ans
                             (cadr ans)
                             (if (< n 2)
                                 1
                                 (let ((res (* n (fact (sub1 n)))))
                                   (set! memo (cons (list n res) memo))
                                   res)))))))
        (/ (fact n) (* (fact r) (fact (- n r))))))))

The memoization is necessary for the factorial since it is used more than once in the formula for the combinatorial.