Say I want to get all combinations of bill/coins denominations that amount to a given value, given also a set of available denominations.
So for instance, for (change 14 #{1 2 5 10})
I'd expect
(
{10 1, 5 0, 2 2, 1 0}
{10 1, 5 0, 2 1, 1 2}
{10 0, 5 2, 2 2, 1 0}
{10 0, 5 2, 2 1, 1 2}
;; ...
)
My attempt was
(defn change [amount denominations]
(let [dens (sort > denominations)
vars (repeatedly (count dens) lvar)]
(run* [q]
(== q (zipmap dens vars))
(everyg #(fd/in % (fd/interval 0 amount)) vars)
(== amount (apply + (map * dens vars))))))
But naturally the last line doesn't work. I haven't found a way to do a sort of reduce
over the vars
sequence, or some other way to set goals that are not valid for each lvar individually, but for the whole (while also doing some operation with external values, amount
and denominations
in this example).
I haven't found a [...] way to set goals that are not valid for each lvar individually, but for the whole (while also doing some operation with external values, amount and denominations in this example).
One way to do this is to define a recursive relation function that takes the logic vars
, the denominations, and the desired sum
, and uses conso
to set goals for each pair of vars
and dens
items:
(defn productsumo [vars dens sum]
(fresh [vhead vtail dhead dtail product run-sum]
(conde
[(emptyo vars) (== sum 0)]
[(conso vhead vtail vars)
(conso dhead dtail dens)
(fd/* vhead dhead product)
(fd/+ product run-sum sum)
(productsumo vtail dtail run-sum)])))
Notice the fresh
logic variables here for the heads and tails of vars
and dens
, a product
to store the product of the head of each for each "pass", and a run-sum
variable that will be used to constrain the total of all the products such they're equal to sum
. The combination of conso
and recursion allows us to set goals for the whole of vars
and dens
.
Then plug that in to your existing function:
(defn change [amount denoms]
(let [dens (sort > denoms)
vars (repeatedly (count dens) lvar)]
(run* [q]
(== q (zipmap dens vars))
(everyg #(fd/in % (fd/interval 0 amount)) vars)
(productsumo vars dens amount))))
And finally get the answers:
(change 14 #{1 2 5 10})
=>
({10 0, 5 0, 2 0, 1 14}
{10 1, 5 0, 2 0, 1 4}
{10 0, 5 1, 2 0, 1 9}
{10 0, 5 0, 2 1, 1 12}
{10 1, 5 0, 2 1, 1 2}
{10 1, 5 0, 2 2, 1 0}
{10 0, 5 0, 2 2, 1 10}
{10 0, 5 2, 2 0, 1 4}
{10 0, 5 1, 2 1, 1 7}
{10 0, 5 0, 2 3, 1 8}
{10 0, 5 0, 2 4, 1 6}
{10 0, 5 1, 2 2, 1 5}
{10 0, 5 0, 2 5, 1 4}
{10 0, 5 2, 2 1, 1 2}
{10 0, 5 0, 2 6, 1 2}
{10 0, 5 1, 2 3, 1 3}
{10 0, 5 0, 2 7, 1 0}
{10 0, 5 2, 2 2, 1 0}
{10 0, 5 1, 2 4, 1 1})
I suspect there may be a more succinct/elegant solution, but this works.