如何对 lvar 序列进行操作

Question

假设我想得到所有 bill/coins 面额的组合，这些面额等于给定的值，还给定了一组可用的面额。

例如，对于 (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 单独无效但对整体无效的目标（同时也在做一些使用外部值的操作，本例中为 amount 和 denominations）。

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

我怀疑可能还有更多 succinct/elegant 解决方案，但这个可行。

如何对 lvar 序列进行操作

How to operate on a sequence of lvars

clojure

logic-programming

clojure-core.logic