Y箱

金種を組みあわせて2ポンドを作る問題。
金額の大きい順に個数を割りあてて樹形図を作るイメージ。

2￡  1￡  ... 

0    0
     1
     2

1    0
     1

2

データ構造体は、
 <残りの金額> <金種ごとの枚数のリスト>
という感じ。

;;
;; Problem 31  : 2011/5/16
;; "Elapsed time: 604.414248 msecs"

;;data structure
(defstruct coin-table
  :rest-amount
  :coin-list)

(defn next-list [in-table coin]
  (for [num (take-while #(<= (* % coin) (:rest-amount in-table)) (iterate inc 0))]
    (struct coin-table
     (- (:rest-amount in-table) (* coin num))
     (assoc (:coin-list in-table) coin num))))
     
(loop  [mid-flow (list (struct coin-table 200 {}))
        coin-list [200 100 50 20 10 5 2]
        result-list ()]
  (if (empty? coin-list)
    (concat result-list mid-flow)
    (let [new-list (mapcat #(next-list % (first coin-list)) mid-flow)]
      (recur (filter #(> (:rest-amount %) 0) new-list)
             (rest coin-list)
             (concat result-list (filter #(<= (:rest-amount %) 0) new-list))))))

;;