clojure - 如何对一系列 lvar 进行操作

Question

假设我想获取达到给定值的所有纸币/硬币面额组合，同时还给出一组可用面额。

例如，对于 (change 14 #{1 2 5 10}) 我期望

(
    {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}
    ;; ...
)

我的尝试是

(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))))))

但最后一行自然不起作用。我还没有找到一种方法来对 vars 序列进行某种 reduce 操作，或者使用其他方法来设置对每个 lvar 单独无效的目标，但对于整体(同时还对外部值进行一些操作，在此示例中，金额和面额)。

Answer 1

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).

实现此目的的一种方法是定义一个递归关系函数，该函数采用逻辑 vars、面额和所需的 sum，并使用 conso 为每对 vars 和 dens 项目设置目标:

(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)])))

请注意此处的 fresh 逻辑变量，用于 vars 和 dens 的头部和尾部，这是一个 product存储每个“pass”的每个头部的乘积，以及一个 run-sum 变量，该变量将用于约束所有乘积的总和，使它们等于 sum。 conso 和递归的结合使我们能够为整个 vars 和 dens 设定目标。

然后将其插入到您现有的函数中:

(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))))

最终得到答案:

(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})

我怀疑可能有更简洁/优雅的解决方案，但这可行。