對seq進行分區 - 在Clojure（或一般Lisp）中遞歸

在我正在開發的一個項目中，我遇到了一個有趣的問題，我很好奇其他解決方案。我正在閱讀「The Little Schemer」，所以我嘗試了一些遞歸技術。我想知道是否有另一種方法來做到這一點與遞歸，也有興趣，如果有一種方法沒有使用遞歸。對seq進行分區 - 在Clojure（或一般Lisp）中遞歸

問題是要採取一個序列，並通過採取每第n個元素將其分割爲seqs序列。例如，這向量：

[ :a :b :c :d :e :f :g :h :i ]

當n = 3的分配將產生SEQ

((:a :d :g) (:b :e :h) (:c :f :i))

和其中n = 4：

((:a :e :i) (:b :f) (:c :g) (:d :h))

等。我用兩個函數解決了這個問題。第一個創建內部seqs，另一個將它們拉到一起。這裏是我的功能：

(defn subseq-by-nth 
    "Creates a subsequence of coll formed by starting with the kth element and selecting every nth element." 
    [coll k n] 
    (cond (empty? coll) nil 
     (< (count coll) n) (seq (list (first coll))) 
     :else (cons (nth coll k) (subseq-by-nth (drop (+ n k) coll) 0 n)))) 

(defn partition-by-nth 
    "" 
    ([coll n] 
    (partition-by-nth coll n n)) 
    ([coll n i] 
     (cond (empty? coll) nil 
     (= 0 i) nil 
     :else (cons (subseq-by-nth coll 0 n) (partition-by-nth (rest coll) n (dec i))))))

我不具有多個元數只是爲遞歸分區按第n個功能完全滿意，但看不到另一種方式。

這似乎對所有的測試用例都很好。這是一個體面的方法嗎？它太複雜了嗎？有沒有辦法做到這一點沒有遞歸或可能在一個單一的遞歸函數？

感謝您的建議。我對Clojure和Lisp都很陌生，所以我隨身攜帶不同的技術。

來源

2012-10-10 Dave Kincaid

我希望有一個更簡單的遞歸定義，更在精神的小策士，但使用take-nth以下功能更加緊湊了不少，因爲你說你有興趣的替代方法：

(defn chop [coll n] 
    (for [i (range n)] 
    (take-nth n (drop i coll))))

滿足你的例子：

(chop [:a :b :c :d :e :f :g :h :i ] 3) 
;= ((:a :d :g) (:b :e :h) (:c :f :i)) 

(chop [:a :b :c :d :e :f :g :h :i ] 4) 
;= ((:a :e :i) (:b :f) (:c :g) (:d :h))

在Clojure中，內置的圖書館會得到你帶來意想不到的;當失敗時，使用明確的遞歸解決方案。這個版本也很懶，您可能希望在任何「longhand」（顯式遞歸）版本中使用lazy-seq或loop...recur來處理大型數據集而不吹動堆棧。

來源

2012-10-10 02:25:24 JohnJ

謝謝，這是真棒！我不知道這可能是那麼容易。就在我認爲我開始明白這一點的時候，我顯示了自己真的很少。 –

我知道這種感覺！ – JohnJ

@DaveKincaid：你應該嘗試使用現有的高階函數來建模你的解決方案，而不是使用遞歸，你一定能夠想出這種簡潔的解決方案:) – Ankur

編輯是因爲原來的答案完全錯過了這一點。

當我第一次看到這個問題時，我認爲應用了clojure.core功能partition（請參閱 ClojureDocs page）。

由於Dave指出分區只適用於原始順序中的元素。 take-nth解決方案顯然更好。僅僅爲了興趣而將分區類型作品的多個序列映射的組合。

(defn ugly-solution [coll n] 
    (apply map list (partition n n (repeat nil) coll))) 

(ugly-solution [:a :b :c :d :e :f :g :h :i] 3) 
;;=> ((:a :d :g) (:b :e :h) (:c :f :i)) 
(ugly-solution [:a :b :c :d :e :f :g :h :i] 4) 
;;=> ((:a :e :i) (:b :f nil) (:c :g nil) (:d :h nil))

來源

2012-10-10 14:25:12

我看到了，但無法弄清楚在這種情況下如何使用它。它似乎總是按照相同的順序進行分區。如果你有辦法做到這一點，我也有興趣看到它。 –

@DaveKincaid是的，你說得很對。重新排序要求意味着分區不起作用。我已經編輯了使用分區的答案，但是使用分區肯定是更好的方法。 –

我要提供這個Common Lisp的循環：

(defun partition-by-nth (list n) 
    (loop :with result := (make-array n :initial-element '()) 
     :for i :upfrom 0 
     :and e :in list 
     :do (push e (aref result (mod i n))) 
     :finally (return (map 'list #'nreverse result))))

來源

2012-10-10 21:32:32 Svante

對seq進行分區 - 在Clojure（或一般Lisp）中遞歸

回答

相關問題