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

Question

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.

score 4 · Answer 1 · edited May 23 '17 at 12:14

4

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.

edited May 23 '17 at 12:14

Community

1
1

answered Aug 05 '14 at 02:06

A. Webb

26,227
1
63
95

score 2 · Answer 2 · answered Aug 04 '14 at 17:02

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

score 2 · Answer 3 · answered Aug 04 '14 at 20:42

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.

score 0 · Answer 4 · answered Aug 04 '14 at 16:24

0

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]]

answered Aug 04 '14 at 16:24

edbond

3,921
19
26

@Alex yes, it may be improved. Will not work with lists imo. Wanted to find simple solution. – edbond Aug 04 '14 at 17:46

score 0 · Answer 5 · answered Aug 04 '14 at 16:35

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.

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

5 Answers5