数え上げ

要件としては

• ある数の両替パターンを全部数え上げたい
• まず、要素の合計がある数以下なリストの集合を取得したい

という事になります。釣り銭のパターンとしては

(define candidate-list '(50 25 10 5 1))

で、例えば 16 が_ある数_としたら make-list という以下の手続きで釣り銭候補は列挙できる。

(define (make-list n l)
  (cond ((null? l) '())
	((>= n (car l)) l)
	(else
	 (make-list n (cdr l)))))

で、ここからが昨晩もハマッてた部分。ちなみに現時点で解に至ってません。

とりあえず

戻りは略しますが以下がでっち上がってます。

(define (enum-candidate lst n candidate)
  (map (lambda (x)
	 (let ((test (append lst (list x))))
	   (cond ((> n (apply + test))
		  (enum-candidate test n (make-list x candidate-list)))
		 ((= n (apply + test)) test)
		 (else '()))))
       candidate))

数え上げと言いつつ解が出ちゃってます。しかも map 使って再帰してるからもの凄いリストが出てきます。今日はもう寝る。