7

私が取り組んでいるプロジェクトで、他の解決策について知りたい興味深い問題に遭遇しました。「TheLittleSchemer」を読んでいる最中なので、再帰的な手法を試しています。再帰を使ってこれを行う別の方法があるかどうか疑問に思っています。また、再帰を使用しないアプローチがあるかどうかにも興味があります。

問題は、シーケンスを取得し、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))

等々。私は2つの関数を使用してこれを解決しました。1つ目は内部シーケンスを作成し、もう1つはそれらをまとめます。これが私の関数です：

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

再帰のためだけに複数のアリティを持つpartition-by-nth関数に完全に満足しているわけではありませんが、別の方法を見つけることはできませんでした。

これは、すべてのテストケースで問題なく機能するようです。これはまともなアプローチですか？複雑すぎませんか？再帰なしで、またはおそらく単一の再帰関数でこれを行う方法はありますか？

提案をありがとう。私はClojureとLispの両方に慣れていないので、さまざまなテクニックを習得しています。

4

3 に答える 3

9

The Little Schemerの精神に近い、より単純な再帰的定義があると思いますが、別のアプローチに興味があると言ったので、次の関数を使用する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では、組み込みのライブラリを使用すると、驚くほど遠くまで行くことができます。それが失敗した場合は、明示的に再帰的なソリューションを使用してください。このバージョンも怠惰です。スタックを壊さずに大規模なデータセットを処理するには、おそらく、lazy-seqまたは任意の「ロングハンド」（明示的に再帰的な）バージョンを使用することをお勧めします。loop...recur

于 2012-10-10T02:25:24.573 に答える
0

元の回答が完全にポイントを逃したために編集されました。

この質問を最初に見たとき、clojure.core関数partitionが適用されていると思いました（ ClojureDocsページを参照）。

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-10T14:25:12.540 に答える
0

私はこのCommonLispループを提供しなければなりません：

(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 に答える