`for`如何在這個遞歸Clojure代碼中工作？

Question

Clojure初學者在這裏。下面是一些代碼，我想了解，從http://iloveponies.github.io/120-hour-epic-sax-marathon/sudoku.html（一個相當不錯的開始Clojure的過程中的一個頁面）：

---

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

但是爲什麼第3行的subset-sum-helper要返回[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表達式枚舉了a-set中的每個元素elem而不是中的current-set，解決方案包含當前集合和元素。而且它正在爲所有這些元素陸續這樣做。因此，從所有解決方案包含的空集開始，它會生成所有這些解。

Answer 2

也許這樣的解釋可以幫助你：

首先，我們可以用最少的代碼實驗的for功能的預期行爲（有和沒有括號），但除去遞歸相關的代碼

用括號：

(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的綁定值。

換句話說，代碼作者需要一個集合，而不是迭代集合作爲它內部的綁定值。於是，她把一套成序列「＃{X}]」

和總結
「爲」功能採用一種或多種結合形式的載體/ 收集-EXPR對 所以，如果你的「collection-expre」是＃{：a}，迭代結果將是（：a），但如果你的「collection-expre」是[＃{：a}]，迭代結果將是（＃{：a}）

對不起，我解釋的冗餘，但很難明確這些細微差別

Answer 3

只是爲了好玩，這裏有一個更清潔soluti上，仍然使用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)))))