Схема: Перечислите все способы внести изменения в 10 Использование списка

Question

Цель: всего: 10 denoms: (10 5 1) возвращение ((10) (5 5) (5 1 1 1 1 1) (1 1 1 1 1 1 1 1 1 1))

Мой код:

(define (changes-list total denoms) 

    (cond 

    ((null? denoms) nil) 

    ((= total 0)) 

    ((> (car denoms) total) (changes-list total (cdr denoms))) 

    (else 

     (if (= total (car denoms)) (cons (list (car denoms)) (changes-list total (cdr denoms))) 
     (append (cons-all (car denoms) (changes-list (- total (car denoms)) denoms)))) 
    ) ) ) 

~~~~~~ Что мой код выхода прямо сейчас: ((10) (5 5) (5 1 1 1 1 1)) Я думаю, что проблема может заключаться в условии, если, когда я вызываю список изменений на (cdr denoms) и который меняет знаки на пустой и выходит, но я не знаю, как fi x это. Вся помощь очень ценится !!

Answer 1

Предполагая, что следующие два условия (в противном случае вы должны проверить параметры):

1. total всегда неотрицательна,
2. denoms сортируется в порядке убывания и последний элемент всегда 1,

здесь возможное решение:

(define (cons-all x lst) 
    (map (lambda (l) (cons x l)) lst)) 

(define (repeat n x) 
    (if (= n 0) 
     '() 
     (cons x (repeat (- n 1) x)))) 

(define (changes-list total denoms) 
    (cond ((= total 0) '(())) 
     ((null? (cdr denoms)) (list (repeat total (car denoms)))) 
     ((< total (car denoms)) (changes-list total (cdr denoms))) 
     (else (append (cons-all (car denoms) (changes-list (- total (car denoms)) denoms)) 
         (changes-list total (cdr denoms)))))) 

(changes-list '6 (2 1)) ; => ((2 2 2) (2 2 1 1) (2 1 1 1 1) (1 1 1 1 1 1)) 

Answer 2

При попытке различные пути которых не каждый будет давать верное решение мне нравится использовать path список для отслеживания пути, и аккумулятор acc только сохранить успешные результаты:

(define (changes-list total denoms) 
    (let iter ((total total) (denoms denoms) (path '()) (acc '())) 
    (cond 
     ((= total 0) (cons (reverse path) acc)) ; the current path lead to a solution => keep path in accumulator 
     ((or (< total 0) (null? denoms)) acc) ; discard path 
     (else 
     (let ((denom (car denoms))) ; first denomination 
     (iter (- total denom)  ; (1) use first denomination 
       denoms 
       (cons denom path) 
       (iter total   ; (2) drop first denomination 
        (cdr denoms) 
        path 
        acc))))))) 

Тестирование:

> (changes-list 10 '(10 5 1)) 
'((10) (5 5) (5 1 1 1 1 1) (1 1 1 1 1 1 1 1 1 1)) 
> (changes-list 6 '(2 1)) 
'((2 2 2) (2 2 1 1) (2 1 1 1 1) (1 1 1 1 1 1))