お釣りの要らない全ての支払い方

awtp.clj

(require '[clojure.test :refer (with-test are run-tests)])

(with-test
  (defn awtp [cs a]
    ((fn f [[h & r] a]
       (cond
         (zero? a) #{{}}
         (nil? h)  #{}
         :else     (set
                     (mapcat (fn [c]
                               (map #(if (pos? c) (assoc % h c) %)
                                    (f r (- a (* c h)))))
                             (range 0 (inc (quot a h)))))))
     (sort-by identity > cs) a))

  (are [cs a r] (= (awtp cs a) r)
    #{1 3} 8 #{{3 2, 1 2} {3 1, 1 5} {1 8}} ; 1円硬貨と3円硬貨があったとすると, 8円の支払いは 3円2枚と1円2枚, 3円1枚と1円5枚, 1円8枚.
    #{2 3} 8 #{{3 2, 2 1} {2 4}}
    #{5 10} 7 #{}
    #{5 10} 23 #{}
    #{10 50 100} 130 #{{100 1, 10 3}
                       {50 2, 10 3}
                       {50 1, 10 8}
                       {10 13}}
    #{10 50 100} 150 #{{100 1, 50 1}
                       {100 1, 10 5}
                       {50 3}
                       {50 2, 10 5}
                       {50 1, 10 10}
                       {10 15}}))

お釣りの要らない全ての支払い方

仕様

貨幣の種類をその金額である正の整数で表すとします.
貨幣の種類の集合 cs と, 金額 a を与えると,
それらの貨幣の種類の集合で可能な, お釣り無く支払える全ての支払い方を返します.
ひとつの支払い方は, 貨幣の種類をキー, その個数を値とするマップで表します.
使わなかった種類の貨幣については, 0枚としてマップに含めるのではなく, マップに含めないものとします.
全ての支払い方は, 支払い方の集合で返します.

(そのうち解説書きます)