7

在我正在进行的一个项目中，我遇到了一个有趣的问题，我对其他解决方案感到好奇。我正在阅读“The Little Schemer”，所以我正在尝试一些递归技术。我想知道是否有另一种使用递归的方法来做到这一点，并且如果有一种不使用递归的方法也很感兴趣。

问题是获取一个序列，并通过获取每个第 n 个元素将其划分为一个 seq 序列。例如这个向量：

[ :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))

等等。我使用两个函数解决了这个问题。第一个创建内部序列，另一个将它们拉在一起。这是我的功能：

(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))))))

我对仅用于递归的具有多个参数的逐个分区函数并不完全满意，但看不到另一种方式。

这似乎适用于所有测试用例。这是一个体面的方法吗？是不是太复杂了？有没有办法在没有递归的情况下或者在单个递归函数中做到这一点？

感谢您的建议。我是 Clojure 和 Lisp 的新手，所以我在学习不同的技术。

4

3 回答 3

9

我希望有一个更简单的递归定义，它更符合The Little Schemer的精神，但是下面的函数 usingtake-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 中，内置库会让您走得更远；如果失败，请使用显式递归解决方案。这个版本也很懒；您可能希望使用lazy-seq或使用loop...recur任何“速记”（显式递归）版本来处理大型数据集而不会破坏堆栈。

于 2012-10-10T02:25:24.573 回答
0

编辑是因为原始答案完全没有抓住重点。

当我第一次看到这个问题时，我认为partition应用了 clojure.core 函数（请参阅 ClojureDocs 页面）。

正如戴夫指出的那样，分区仅适用于原始顺序的元素。take-nth解决方案显然更好。只是为了感兴趣，将 map 与从分区类型的作品中派生的多个序列相结合。

(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-10T14:25:12.540 回答
0

我必须提供这个 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-10T21:32:32.847 回答