dfs.clj

; http://d.hatena.ne.jp/anton0825/20101229/1293213099
; 大体そのまま移植しただけ
; dfs なのにstackを用意していないように見えるのは
; 言語のstackをstackとして利用しているため。
(defn dfs [k [fs & res] sum]
  (println sum fs res)
  (if fs
    (or (dfs k res (+ fs sum))
        (dfs k res sum))
    (= sum k)))

(dfs 7 [1 2 3 4 5] 0)
;; 0 1 (2 3 4 5)
;; 1 2 (3 4 5)
;; 3 3 (4 5)
;; 6 4 (5)
;; 10 5 nil
;; 15 nil nil
;; 10 nil nil
;; 6 5 nil
;; 11 nil nil
;; 6 nil nil
;; 3 4 (5)
;; 7 5 nil
;; 12 nil nil
;; 7 nil nil
;; => true

;; sum が k を超えていたらもうfalseは決定なので無駄に計算をしないようにする
(defn dfs2 [k [fs & res] sum]
  (when (<= sum k)
    (println sum k fs res)
    (if fs
      (and 
       (or (dfs2 k res (+ fs sum))
           (dfs2 k res sum)))
      (= sum k))))

(dfs2 7 [1 2 3 4 5] 0)
;; 0 7 1 (2 3 4 5)
;; 1 7 2 (3 4 5)
;; 3 7 3 (4 5)
;; 6 7 4 (5)
;; 6 7 5 nil
;; 6 7 nil nil
;; 3 7 4 (5)
;; 7 7 5 nil
;; 7 7 nil nil
;; => true

; 言語のstackを食いつぶさないように、stackを用意して引数で渡す。
; 基本的には難しくなりがちなので問題が小さいなら上記の簡単なバージョンで済ますかも
(defn dfs3 [k lis]
  (loop [[fs & res] [{:sum 0 :items lis}]]
    (when fs
      (let [{:keys [sum items]} fs
            [first-item & rest-items] items]
        (println res sum items first-item rest-items)
        (cond (= k sum) true
              (or (< k sum)
                  (nil? items)) (recur res)
              items (recur (conj res
                                 {:sum (+ sum first-item) :items rest-items}
                                 {:sum sum :items rest-items})))))))


(dfs3 7 [1 2 3 4 5])
;; nil 0 [1 2 3 4 5] 1 (2 3 4 5)
;; ({:sum 1, :items (2 3 4 5)}) 0 (2 3 4 5) 2 (3 4 5)
;; ({:sum 2, :items (3 4 5)} {:sum 1, :items (2 3 4 5)}) 0 (3 4 5) 3 (4 5)
;; ({:sum 3, :items (4 5)} {:sum 2, :items (3 4 5)} {:sum 1, :items (2 3 4 5)}) 0 (4 5) 4 (5)
;; ({:sum 4, :items (5)} {:sum 3, :items (4 5)} {:sum 2, :items (3 4 5)} {:sum 1, :items (2 3 4 5)}) 0 (5) 5 nil
;; ({:sum 5, :items nil} {:sum 4, :items (5)} {:sum 3, :items (4 5)} {:sum 2, :items (3 4 5)} {:sum 1, :items (2 3 4 5)}) 0 nil nil nil
;; ({:sum 4, :items (5)} {:sum 3, :items (4 5)} {:sum 2, :items (3 4 5)} {:sum 1, :items (2 3 4 5)}) 5 nil nil nil
;; ({:sum 3, :items (4 5)} {:sum 2, :items (3 4 5)} {:sum 1, :items (2 3 4 5)}) 4 (5) 5 nil
;; ({:sum 9, :items nil} {:sum 3, :items (4 5)} {:sum 2, :items (3 4 5)} {:sum 1, :items (2 3 4 5)}) 4 nil nil nil
;; ({:sum 3, :items (4 5)} {:sum 2, :items (3 4 5)} {:sum 1, :items (2 3 4 5)}) 9 nil nil nil
;; ({:sum 2, :items (3 4 5)} {:sum 1, :items (2 3 4 5)}) 3 (4 5) 4 (5)
;; ({:sum 7, :items (5)} {:sum 2, :items (3 4 5)} {:sum 1, :items (2 3 4 5)}) 3 (5) 5 nil
;; ({:sum 8, :items nil} {:sum 7, :items (5)} {:sum 2, :items (3 4 5)} {:sum 1, :items (2 3 4 5)}) 3 nil nil nil
;; ({:sum 7, :items (5)} {:sum 2, :items (3 4 5)} {:sum 1, :items (2 3 4 5)}) 8 nil nil nil
;; ({:sum 2, :items (3 4 5)} {:sum 1, :items (2 3 4 5)}) 7 (5) 5 nil
;; true