CODEWITHSUNDEEP
algorithmclojure
zetafish
zetafish

Reputation: 2412

How do I partition a sequence into increasing sub sequences in Clojure?

I have a sequence of integers and I would like to partition them into increasing segments and I want to have as little as possible segments. So I want to have 

(segmentize [1 2 3 4 3 8 9 1 7] <=)
;=> [[1 2 3 4][3 8 9][1 7]]

I have implemented segmentize as follows:

(defn segmentize [col lte]
  (loop [col col s [] res []]
    (cond (empty? col) (conj res s)
          (empty? s) (recur (rest col) (conj s (first col)) res)
          (lte (last s) (first col)) (recur (rest col) (conj s (first col)) res)
          :else (recur col [] (conj res s)))))

But I was wondering if there is already some handy clojure function that does exactly this, or if there is a more idiomatic way to do this.

Upvotes: 3

Views: 535

Answers (5)

A. Webb
A. Webb

Reputation: 26446

You can build this with partition-by

(defn segmentize [cmp coll]
  (let [switch (reductions = true (map cmp coll (rest coll)))]
    (map (partial map first) (partition-by second (map list coll switch)))))

(segmentize <= [1 2 3 4 3 8 9 1 7])
;=> ((1 2 3 4) (3 8 9) (1 7))

The first two maps of the last line may be changed to mapv if you really want vectors rather than lazy sequences.

Upvotes: 4

amalloy
amalloy

Reputation: 91857

This is a special case of some of the sequence-handling functions in org.flatland/useful, specifically flatland.useful.seq/partition-between: 

(partition-between (partial apply >) xs)

If you require a from-scratch implementation with no external dependencies, I'd prefer dAni's answer.

Upvotes: 2

DanLebrero
DanLebrero

Reputation: 8593

Another lazy implementation. Basically find out how many consecutive pairs of numbers return true for the "lte" function (take-while + segment) and then split the original collection by that number. Repeat with the reminder collection:

(defn segmentize
 [coll lte]
 (lazy-seq
  (when-let [s (seq coll)]
    (let [pairs-in-segment (take-while (fn [[a b]] (lte a b)) (partition 2 1 s))
          [segment reminder] (split-at (inc (count pairs-in-segment)) s)]
      (cons segment
            (segmentize reminder lte))))))

Upvotes: 2

Alex
Alex

Reputation: 13941

Because everybody loves lazy sequences:

(defn segmentize [coll cmp]
  (if-let [c (seq coll)]
    (lazy-seq 
     (let [[seg rem] (reduce (fn [[head tail] x]
                               (if (cmp (last head) x)
                                 [(conj head x) (next tail)]
                                 (reduced [head tail])))
                             [(vec (take 1 c)) (drop 1 c)]
                             (drop 1 c))]
       (cons seg (segmentize rem cmp))))))

The code to compute each segment could probably be made a little less verbose using loop/recur, but I tend to find reduce more readable most of the time.

Upvotes: 0

edbond
edbond

Reputation: 3951

Here is my version of segmentize (I called in split-when):

(defn split-when [f s]
  (reduce (fn [acc [a b]]
            (if (f b a)
              (conj acc [b])
              (update-in acc [(dec (count acc))] conj b)))
          [[(first s)]]
          (partition 2 1 s)))

(split-when < [1 2 3 4 3 8 9 1 7])

;; [[1 2 3 4] [3 8 9] [1 7]]

Upvotes: 0

Related Questions