不使用连续整数的分区编号

Question

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

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

实现list-分区程序，其中列出了所有的办法 分区正整数总不使用连续的整数。每个分区的 内容必须按降序排列。提示：定义一个帮助程序来构建分区。内置附录 过程将创建一个包含两个参数列表的所有元素的列表。 questions.scm中的cons-all过程向列表中的每个列表添加第一个元素。

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

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

不知道方案，但递归代伪代码可能看起来像：

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]);