不使用连续整数的数字分区

Question

我正在关注cs61a 2015年春季课程。

方案项目中的问题之一是：

实现列表分区过程，该过程列出了所有方法 在不使用连续整数的情况下对正整数总计进行分区。这 每个分区的内容必须按降序列出。 提示：定义一个帮助程序过程来构造分区。内置追加 过程创建一个包含两个参数列表的所有元素的列表。 questions.scm 中的 cons-all 过程将第一个元素添加到列表列表中的每个列表。

数字 5 有 4 个不包含连续整数的分区：

5

4、1

3， 1， 1

1， 1， 1， 1， 1

由于连续，不包括以下 5 个分区 整数：

3， 2

2， 2， 1

2， 1， 1， 1

我找到了一个解决方案，但无法理解

;; List all ways to partition TOTAL without using consecutive numbers.
(define (apply-to-all proc items)
(if (null? items)
'() 
(cons (proc (car items))
(apply-to-all proc (cdr items)))))
(define (cons-all first rests)
(apply-to-all (lambda (rest) (cons first rest)) rests))
(define (caar x) (car (car x)))
(define (cadr x) (car (cdr x)))
(define (cddr x) (cdr (cdr x)))
(define (cadar x) (car (cdr (car x))))
(define (cdar x) (cdr (car x)))
(define (partitions-r a b)
(if (= a 0) nil
(append (cons-all a (list-partitions b))
(cons-f (partitions-r (- a 1) (+ b 1))
))
))
(define (cons-f lst)
(cond 
((eq? lst nil) nil)
((eq? (cdar lst) nil) lst)
((< (caar lst) (cadar lst)) (cons-f (cdr lst)))
((= (caar lst) (+ 1 (cadar lst))) (cons-f (cdr lst)))
(else (cons (car lst) (cons-f (cdr lst))))
))
(define (list-partitions total)
(cond ((= total 1) '((1)) )
((= total 0) '(()) )
(else (append nil (partitions-r total 0)))
))
; For these two tests, any permutation of the right answer will be accepted.
(list-partitions 5)
; expect ((5) (4 1) (3 1 1) (1 1 1 1 1))
(list-partitions 7)
; expect ((7) (6 1) (5 2) (5 1 1) (4 1 1 1) (3 3 1) (3 1 1 1 1) (1 1 1 1 1 1 1))

函数分区-r 和 cons-f 有什么作用？ 谢谢！

Answer 1

不知道 Scheme，但伪代码中的递归生成可能如下所示：

function Partitions(N, LastValue, list):
if N = 0 
print list
else
for i from  Min(LastValue, N) downto  1
if (i != LastValue - 1)    //reject consecutive number
Partitions(N - i, i, list  + [i]);