“How”在这个递归Clojure代码中是如何工作的？

Question

这里的新手。下面是一些我正在尝试理解的代码，来自http://iloveponies.github.io/120-hour-epic-sax-marathon/sudoku.html (一页相当不错的开始部分)：

Subset sum is a classic problem. Here’s how it goes. You are given:

    a set of numbers, like #{1 2 10 5 7}
    and a number, say 23

and you want to know if there is some subset of the original set that sums up to the target. 
We’re going to solve this by brute force using a backtracking search.

Here’s one way to implement it:

(defn sum [a-seq]
  (reduce + a-seq))

(defn subset-sum-helper [a-set current-set target]
  (if (= (sum current-set) target)
    [current-set]
    (let [remaining (clojure.set/difference a-set current-set)]
      (for [elem remaining
            solution (subset-sum-helper a-set
                                        (conj current-set elem)
                                        target)]
        solution))))

(defn subset-sum [a-set target]
  (subset-sum-helper a-set #{} target))

So the main thing happens inside subset-sum-helper. First of all, always check if we have found 
a valid solution. Here it’s checked with

  (if (= (sum current-set) target)
    [current-set]

If we have found a valid solution, return it in a vector (We’ll see soon why in a vector). Okay, 
so if we’re not done yet, what are our options? Well, we need to try adding some element of 
a-set into current-set and try again. What are the possible elements for this? They are those 
that are not yet in current-set. Those are bound to the name remaining here:

    (let [remaining (clojure.set/difference a-set current-set)]

What’s left is to actually try calling subset-sum-helper with each new set obtainable 
in this way:

      (for [elem remaining
            solution (subset-sum-helper a-set
                                        (conj current-set elem)
                                        target)]
        solution))))

Here first elem gets bound to the elements of remaining one at a time. For each elem, 
solution gets bound to each element of the recursive call

            solution (subset-sum-helper a-set
                                        (conj current-set elem)
                                        target)]

And this is the reason we returned a vector in the base case, so that we can use for 
in this way.

果然，(subset-sum #{1 2 3 4} 4)返回(#{1 3} #{1 3} #{4})。

但是为什么subset-sum-helper的第3行必须返回[current-set]？这难道不是([#{1 3}] [#{1 3}] [#{4}])的最终答案吗？

我尝试删除第3行中的括号，使函数开始如下：

(defn subset-sum-helper [a-set current-set target]
  (if (= (sum current-set) target)
    current-set
    (let ...

现在，(subset-sum #{1 2 3 4} 4)返回(1 3 1 3 4)，这使let看起来不累加三组#{1 3}、#{1 3}和#{4}，而只是“裸”数字，给出了(1 3 1 3 4)。

因此，subset-sum-helper在递归计算中使用列表理解for，我不知道发生了什么。当我尝试可视化这个递归计算时，我发现自己会问：“那么，当

(subset-sum-helper a-set
   (conj current-set elem)
   target)

不返回答案，因为考虑到答案的起点是不可能的？“(我的最佳猜测是它返回[]或类似的东西)，我不明白教程作者在他写的时候是什么意思，”这就是我们在基本情况下返回向量的原因，这样我们就可以这样使用for。

我非常感谢你能帮我的忙。谢谢!

Answer 1

subset-sum-helper函数总是返回一系列解决方案。当不满足target时，for表达式末尾的solution正文将枚举这样的序列。当满足target时，只能返回一个解决方案：current-set参数。它必须作为一个元素的序列返回。有许多方法可以做到这一点：

[current-set] ; as given - simplest
(list current-set)
(cons current-set ())
(conj () current-set)
...

如果您立即从subset-sum-helper返回(没有递归)，您将看到向量：

=> (subset-sum #{} 0)
[#{}]

否则，您将看到for生成的序列，其打印方式类似于列表：

=> (subset-sum (set (range 1 10)) 7)
(#{1 2 4}
 #{1 2 4}
 #{1 6}
 #{1 2 4}
 #{1 2 4}
 #{2 5}
 #{3 4}
 #{1 2 4}
 #{1 2 4}
 #{3 4}
 #{2 5}
 #{1 6}
 #{7})

当不可能回答时，subset-sum-helper返回一个空序列：

=> (subset-sum-helper #{2 4 6} #{} 19)
()

再次，这是打印好像它是一个清单。

该算法存在以下问题：

• 它为一个解决方案(count s) s多次找到每个解的阶乘因子。
• 如果采用的元素elem超调了目标，它就会徒劳无益地尝试添加remaining集合的每一个排列。

如果我们稍微重铸代码，代码就更容易理解。

subset-sum-helper的递归调用完整地传递第一个和第三个参数。如果我们使用letfn使这个函数成为subset-sum的本地函数，我们可以不使用这些参数:它们是从上下文中获取的。现在看起来是这样：

(defn subset-sum [a-set target]
  (letfn [(subset-sum-helper [current-set]
             (if (= (reduce + current-set) target)
                 [current-set]
                 (let [remaining (clojure.set/difference a-set current-set)]
                         (for [elem remaining
                               solution (subset-sum-helper (conj current-set elem))]
                             solution))))]
      (subset-sum-helper #{})))

..。其中，对sum函数的单个调用是内联展开的。

现在非常清楚的是，subset-sum-helper正在返回包含其单个current-set参数的解决方案。for表达式为不在current-set中的a-set的每个元素枚举包含当前集和元素的解决方案。而且它正在为所有这些因素接连这样做。因此，从所有解决方案都包含的空集开始，它生成所有的解决方案。

Answer 2

也许这个解释能帮你：

首先，我们可以在最小的代码中实验为函数的预期行为(带括号和不带括号)，但去掉递归相关的代码。

带括号的：

(for [x #{1 2 3}
      y [#{x}]]
  y)
=> (#{1} #{2} #{3})

没有括号的：

(for [x #{1 2 3}
      y #{x}]
  y)
=> (1 2 3)

带括号和更多元素的***

(for [x #{1 2 3}
      y [#{x}  :a :b :c]]
  y)
=> (#{1} :a :b :c #{2} :a :b :c #{3} :a :b :c)

因此，您需要(在这种情况下)括号，以避免迭代集。

如果不使用括号，就会有"x“作为y的绑定值，如果使用括号，则会有#{x}作为y的绑定值。

换句话说，代码创建者需要一个集合，而不是在其for中作为绑定值迭代一个集合。所以她把一个集合放入一个序列"#{x}“

与综述

"for“函数接受一个或多个binding-form/collection-expr对的向量，因此如果您的”集合-表达式“为#{:a}，则迭代结果将为(:a)，但如果您的”集合-表达式“为#{:a}，则迭代结果为(#{:a})。

抱歉，我的解释有些多余，但很难弄清楚这些细微差别

Answer 3

为了好玩，这里有一个更干净的解决方案，仍然使用for：

(defn subset-sum [s target]
  (cond
    (neg? target) ()
    (zero? target) (list #{})
    (empty? s) ()
    :else (let [f (first s), ns (next s)]
            (lazy-cat
              (for [xs (subset-sum ns (- target f))] (conj xs f))
              (subset-sum ns target)))))