algorithm - 计算数字的不同方法

Question

我需要编写一个函数，返回可以将 n(n 是自然数)写为自然数之和的方法数。 例如:4可以写成1+1+1+1、1+1+2、2+2、3+1、4。 我写了一个返回所有选项数量的函数，但没有考虑到 1 + 1 + 2 和 2 + 1 + 1(以及所有类似情况)的可能性是相等的。所以对于 n=4，它返回 8 而不是 5。 这是我的功能:

(define (possibilities n)
   (define (loop i)
      (cond [(= i n) 1]
         [(> i n) 0]
         [(+ (possibilities (- n i)) (loop (+ i 1)))]))
     (cond [(< n 1) 0]
        [#t (loop 1)]))

能否请您帮我修复我的功能，以便它按应有的方式工作。谢谢。

Answer 1

这是一个众所周知的函数，它叫做 partition function P , 它的可能值被引用为 A000041在整数序列的在线百科全书中。

一个简单的解决方案(不是最快的!)是使用这个辅助函数，它将 n 的写作方式的数量表示为恰好 k 项的总和:

(define (p n k)
  (cond ((> k n) 0)
        ((= k 0) 0)
        ((= k n) 1)
        (else 
         (+ (p (sub1 n) (sub1 k))
            (p (- n k) k)))))

然后我们只需要添加可能的结果，注意边缘情况:

(define (possibilities n)
  (cond ((negative? n) 0)
        ((zero? n) 1)
        (else
         (for/sum ([i (in-range (add1 n))])
           (p n i)))))

例如:

(map possibilities (range 11))
=> '(1 1 2 3 5 7 11 15 22 30 42)