algorithm - 计算数字的不同方法

我需要写一个函数，它将返回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)]))

你能帮我修理一下我的功能吗，这样它就可以工作了。谢谢您。

最佳答案

这是一个众所周知的函数，它被称为partition function P，它的可能值在整数序列的在线百科全书中被引用为A000041。
一个简单的解决方案（不是最快的！）将使用这个helper函数，它将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)

关于algorithm - 计算数字的不同方法，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/28013100/