algorithm - 如何写一个scheme程序，以n和sum作为参数，并显示所有可以求和的数字(从1到n)？

Question

如何写一个scheme程序，以n和sum为参数，并显示所有可以求和的数字(从1到n)？像这样:

(找到 10 10)

((10) (9 , 1) (8 , 2) (7 , 3) (7 ,2 , 1) (6 ,4) (6 , 3, 1) (5 , 4 , 1) (5 , 3 , 2) (4 ,3 ,2 ,1))

我找到了一个:

(define (find n sum) 
  (cond ((<=  sum 0) (list '())) 
        ((<= n 0) '()) 
        (else (append 
                 (find (- n 1) sum) 
                 (map (lambda (x) (cons n x)) 
                  (find (- n 1) (- sum n)))))))

但是效率很低，我想要一个更好的。谢谢。

Answer 1

您正在寻找的算法称为 integer partition .我在 my blog 有几个实现.

编辑: Oscar 恰本地批评了我不完整的回答。作为忏悔，我提供这个答案，希望能澄清一些事情。

我喜欢 Oscar 对流的使用——作为 SRFI-41 的作者我应该。但是扩大 powerset 只是为了丢弃大部分结果似乎是一种落后的解决问题的方法。我喜欢 GoZoner 的简单回答，但不喜欢它的低效率。

让我们从 GoZoner 的回答开始，我在下面进行了一些小的改动，将其重现:

(define (fs n s)
  (if (or (<= n 0) (<= s 0)) (list)
    (append (if (= n s) (list (list n))
              (map (lambda (xs) (cons n xs))
                   (fs (- n 1) (- s n))))
            (fs (- n 1) s))))

这会产生一个输出集列表:

> (fs 10 10)
((10) (9 1) (8 2) (7 3) (7 2 1) (6 4) (6 3 1) (5 4 1) (5 3 2) (4 3 2 1))

该函数的一个简单变体生成计数而不是集合列表，这将是本答案其余部分的重点:

(define (f n s)
  (if (or (<= s 0) (<= n 0)) 0
    (+ (if (= n s) 1
         (f (- n 1) (- s n)))
       (f (- n 1) s))))

下面是该函数的示例运行，包括我古老而缓慢的家用电脑上的计时:

> (f 10 10)
10
> (time (f 100 100)
(time (f 100 ...))
    no collections
    1254 ms elapsed cpu time
    1435 ms elapsed real time
    0 bytes allocated
444793

这很慢；尽管它适用于小输入，但评估 (f 1000 1000) 是无法忍受的，因为该算法是指数级的。问题与朴素的斐波那契算法相同；相同的子问题一次又一次地重新计算。

该问题的常见解决方案是记忆化。幸运的是，我们在 Scheme 中编程，这使得将 memoization 封装在宏中变得容易:

(define-syntax define-memoized
  (syntax-rules ()
    ((_ (f args ...) body ...)
      (define f
        (let ((results (make-hash hash equal? #f 997)))
          (lambda (args ...)
            (let ((result (results 'lookup (list args ...))))
              (or result
                  (let ((result (begin body ...)))
                    (results 'insert (list args ...) result)
                    result)))))))))

我们使用 hash tables来 self 的 Standard Prelude和 universal hash function来 self 的 blog .然后编写函数的内存版本是一件简单的事情:

(define-memoized (f n s)
  (if (or (<= s 0) (<= n 0)) 0
    (+ (if (= n s) 1
         (f (- n 1) (- s n)))
      (f (- n 1) s))))

这不是很漂亮吗？唯一的变化是在函数的定义中添加了-memoized；所有的参数和函数体都是一样的。但是性能大大提高:

> (time (f 100 100))
(time (f 100 ...))
    no collections
    62 ms elapsed cpu time
    104 ms elapsed real time
    1028376 bytes allocated
444793

这是一个数量级的改进，几乎毫不费力。

但这还不是全部。由于我们知道问题具有“最优子结构”，因此我们可以使用动态规划。 Memoization 自上而下工作，并且必须暂停当前级别的递归，计算(直接或通过查找)较低级别的解决方案，然后在当前递归级别恢复计算。另一方面，动态规划是自下而上的，因此子解决方案在需要时始终可用。这是我们函数的动态规划版本:

(define (f n s)
  (let ((fs (make-matrix (+ n 1) (+ s 1) 0)))
    (do ((i 1 (+ i 1))) ((< n i))
      (do ((j 1 (+ j 1))) ((< s j))
        (matrix-set! fs i j
          (+ (if (= i j)
                 1
                 (matrix-ref fs (- i 1) (max (- j i) 0)))
             (matrix-ref fs (- i 1) j)))))
    (matrix-ref fs n s)))

我们使用了 matrix functions我的Standard Prelude .这比将 -memoized 添加到现有函数要多得多，但返回是运行时间又减少了一个数量级:

> (time (f 100 100))
(time (f 100 ...))
    no collections
    4 ms elapsed cpu time
    4 ms elapsed real time
    41624 bytes allocated
444793
> (time (f 1000 1000))
(time (f 1000 ...))
    3 collections
    649 ms elapsed cpu time, including 103 ms collecting
    698 ms elapsed real time, including 132 ms collecting
    15982928 bytes allocated, including 10846336 bytes reclaimed
8635565795744155161506

我们已经从 1254 毫秒减少到 4 毫秒，这是一个相当惊人的改进范围；最终程序在时间和空间上都是 O(ns)。您可以在 运行程序http://programmingpraxis.codepad.org/Y70sHPc0 ，其中包括我的 blog 中的所有库代码.

作为特别的奖励，这里是 define-memoized 宏的另一个版本。它使用 a-lists 而不是哈希表，所以它比上面给出的版本慢很多，但是当底层计算很耗时，而你只是想要一种简单的方法来改进它时，这可能正是你所需要的:

(define-syntax define-memoized
  (syntax-rules ()
    ((define-memoized (f arg ...) body ...)
      (define f
        (let ((cache (list)))
          (lambda (arg ...)
            (cond ((assoc `(,arg ...) cache) => cdr)
            (else (let ((val (begin body ...)))
                    (set! cache (cons (cons `(,arg ...) val) cache))
                    val)))))))))

对于刚刚学习 Scheme 的人来说，这是在 cond 子句中很好地使用准引号和 => 运算符。我不记得我是什么时候写那个函数的——我已经把它搁置多年了——但当我只需要一个快速而肮脏的内存而不关心哈希时，它救了我很多次表和通用哈希函数。

这个答案会出现tomorrow在我的 blog .请顺路参观一下。