partition de nombre sans utiliser d'entiers consécutifs

Question

Je suis la classe cs61a printemps 2015.

Un des problèmes dans le projet de schéma est:

Mettre en oeuvre la procédure liste-partitions, qui répertorie toutes les façons de partition un total entier positif sans utiliser des entiers consécutifs. Le contenu de chaque partition doit être répertorié dans l'ordre décroissant. Indice: Définissez une procédure d'assistance pour construire des partitions. La procédure intégrée append crée une liste contenant tous les éléments de deux listes d'arguments. La procédure cons-all dans questions.scm ajoute un premier élément à chaque liste dans une liste de listes.

Le numéro 5 a 4 partitions qui ne contiennent pas des nombres entiers consécutifs:

4, 1

3, 1, 1

1, 1, 1, 1, Les partitions suivantes de 5 ne sont pas incluses en raison des entiers consécutifs :

3, 2

2, 2, 1

2, 1, 1, 1

J'ai trouvé une solution mais ne peut pas le comprendre

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

Qu'est-ce que les partitions de fonction -r et cons-f faire? Merci beaucoup!

Answer 1

Je ne sais pas le schéma, mais la génération récursive en pseudocode pourrait ressembler à:

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