PasteRack.org
Paste # 26945
2014-06-28 05:59:11

Fork as a new paste.

Paste viewed 516 times.


Embed:

partitions1.rkt

  1. #lang typed/racket/base
  2. (provide partitions
  3.          reset-partitions-cache)
  4.  
  5. ;;; Partitions are computed using Euler's algorithm:
  6.  
  7. ;                k            k(3k+1)              k(3k-1)
  8. ; p(n) = sum (-1)   [ p( n - --------- ) + p( n - --------- ) ]
  9. ;        k>=1                    2                    2
  10.  
  11. ; http://en.wikipedia.org/wiki/Partition_(number_theory)
  12.  
  13.  
  14. (define cache (make-hash '((0 . 1))))
  15.  
  16. ( : reset-partitions-cache : -> Void)
  17. (define (reset-partitions-cache)
  18.   (set! cache (make-hash '((0 . 1)))))
  19.  
  20. (: partitions : Integer -> Integer)
  21. (define (partitions n)
  22.   (define p partitions)
  23.   (hash-ref! cache n
  24.              (λ ()
  25.                (: loop1 : Integer Integer Integer -> Integer)
  26.                (define (loop1 k m s)
  27.                  (cond [(< m 0) s]
  28.                        [else (loop1 (+ k 1) (- m (+ (* 3 k) 1))
  29.                                     (if (odd? k) (+ s (p m)) (- s (p m))))]))
  30.                (: loop2 : Integer Integer Integer -> Integer)
  31.                (define (loop2 k m s)
  32.                  (cond [(< m 0) s]
  33.                        [else   (loop2 (- k 1)
  34.                                       (+ m (* 3 k) -2)
  35.                                       (if (odd? k) (+ s (p m)) (- s (p m))))]))
  36.                (+ (loop1  1 (- n 1) 0)
  37.                   (loop2 -1 (- n 2) 0)))))
  38.  
  39. (time (partitions 10000))

=>