Clojure中的懶惰帕斯卡三角形

我想在Clojure中編寫一個簡潔，懶惰的Pascal's Triangle，旋轉使得行/列遵循三角形的對角線。也就是說，我要產生懶惰seqs以下懶惰序列：Clojure中的懶惰帕斯卡三角形

((1 1 1 1 ...) 
(1 2 3 4 ...) 
(1 3 6 10 ...) 
... 
)

我寫的代碼是：

(def pascal 
    (cons (repeat 1) 
     (lazy-seq 
      (map #(map + %1 %2) 
       (map #(cons 0 %) (rest pascal))) 
       pascal 
     )))

使每一行是通過將形成右移它自己的版本到前一行。問題是，它永遠不會超過第一行，因爲那時(map #(cons 0 %) (rest pascal)))是空的。

=> (take 5 (map #(take 5 %) pascal)) 
((1 1 1 1 1))

什麼是明智的解決方法？我在Clojure編程方面相當陌生，並且思考它涉及的問題的方式非常不同，所以我非常感謝任何有經驗的人提出的建議。

來源

2013-03-09 Luke Hewitt

簡潔慵懶

(def pascal (iterate (partial reductions +') (repeat 1))) 

(map (partial take 5) (take 5 pascal)) 
;=> ((1 1 1 1 1) 
; (1 2 3 4 5) 
; (1 3 6 10 15) 
; (1 4 10 20 35) 
; (1 5 15 35 70))

但是太懶？

(take 5 (nth pascal 10000)) 
;=> StackOverflowError

再次嘗試

(take 5 (nth pascal 10000)) 
;=> (0)

嗯，哦，重新開始，並嘗試，再嘗試

(def pascal (iterate (partial reductions +') (repeat 1))) 
(count (flatten (map (partial take 5) (take 100000 pascal)))) 
;=> 500000

現在這些都在你的堆

(take 5 (nth pascal 100000)) 
;=> (1 100001 5000150001 166676666850001 4167083347916875001)

來源

2013-03-09 13:30:46

+1。你知道爲什麼第二次調用'（拿5（第n次pascal 10000））'給第一個結果以不同的結果嗎？ StackOverFlowError以某種方式破壞序列？另外，在'+'之後有一個'''符號，我不認爲你需要它。 – OpenSauce 2013-03-12 10:51:32

@OpenSauce準確地說，這表明只調用lazy-seq的第一次和緩存結果行爲。那個產生這個異常的地方不會被再次調用，並且由REPL處理的異常緩存了僞造結果。 +'會在需要時自動升級到'BigInt'。如果我採用了6而不是5，那麼就會顯示出來。 – 2013-03-12 12:02:27

帕斯卡不應該是一個var，而應該是一個產生的函數無限的seqs。

Check out this question for usage on lazy-seq

BTW，試試這個：

(defn gennext [s sum] 
    (let [newsum (+ (first s) sum)] 
    (cons newsum 
      (lazy-seq (gennext (rest s) newsum))))) 

(defn pascal [s] 
    (cons s 
     (lazy-seq (pascal (gennext s 0)))))

enter image description here

（帕斯卡（重複1））爲您提供整數溢出異常但這意味着它產生了無限seqs。您可以使用+'來使用大整數。

來源

2013-03-09 15:53:04 yehe

@A。韋伯的代碼更好，他使用我不知道的減少。 – yehe 2013-03-09 16:01:07

你的解釋可能對於OP來說更有幫助:)。但是我會避免使用'seq'作爲綁定符號，因爲它已經是一個常用的函數。 – 2013-03-09 16:04:22

Clojure中的懶惰帕斯卡三角形

回答

相關問題