不使用連續整數的分區編號

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