In clojure how to partition an array of sorted integers into contiguous partitions?

I'd like to partition an array of sorted integers into contiguous partitions.

The following ruby:

[1,2,3,8,9,10,99].slice_when { |x, y| y > x + 1 }.to_a

Outputs:

[[1, 2, 3], [8, 9, 10], [99]]

How can I do this in clojure?

I tried using partition-by, but AFAIK it only takes one argument.

You have to save somewhere that previous element. In this case, you can do:

(defn slice [coll]
  (let [prev (atom (first coll))]
    (->> coll
         (partition-by #(< (inc @prev) (reset! prev %))))))

(slice [1 2 3 8 9 10 99])
=> ((1 2 3) (8 9 10) (99))

If you also want to provide that function, you will have to write some reduce-based solution:

(defn slice-when [pred coll]
  (->> coll
       (reduce (fn [acc current]
                 (if-let [previous (peek (peek acc))]
                   (if (pred previous current)
                     (conj acc [current])
                     (conj (pop acc) (conj (peek acc) current)))
                   (conj acc [current])))
               [])))

Example:

(slice-when (fn [x y] (> y (inc x))) 
            [1 2 3 8 9 10 99])
=> [[1 2 3] [8 9 10] [99]]

you could also mark all the split points, and then just partition with them

(defn split-when [pred data]  
  (when-let [[x & xs] (seq data)]
    (->> (mapcat (fn [a b] (if (pred a b) [::split b] [b])) 
                 data xs)
         (cons x)
         (partition-by #{::split})
         (take-nth 2))))

user> (split-when (complement (comp #{-1} -)) [1 5 6 7 9 10 22])
;;=> ((1) (5 6 7) (9 10) (22))

otherwise you can collect all the indices where you should split and pass over to subvec:

 (defn split-when [pred data]   
   (when (seq data)
     (let [splits (keep-indexed (fn [i [a b]] (when (pred a b) (inc i)))
                                (partition 2 1 data))
           indices `[0 ~@splits ~(count data)]]
       (map (partial subvec (vec data)) indices (rest indices)))))

user> (split-when (complement (comp #{-1} -)) [1 5 6 7 9 10 22])
;;=> ([1] [5 6 7] [9 10] [22])

I wrote a general version shown below.

It splits the data vector at all possible points, presenting the sub-vectors to a predicate function that looks like:

(fn [data1 data2] ...)

It keeps track of all the indexes where the pred returns true, then uses reduce and subvec to accumulate the result. I've included a unit test.

(ns tst.demo.core
  (:use demo.core tupelo.core tupelo.test))

; We use `split-at` to partition the coll. Given a coll like [0 1 2], it makes
; no sense to give degenerate splits like {:data1 [] :data2 [0 1 2]}
; or {:data1 [0 1 2] :data2 []}. So, we need the split point in the range [1..(N-1)]
(verify
  (let [data   [0 1 2]
        N      (count data)
        result (forv [i (thru N)]
                 (let [[data1 data2] (split-at i data)]
                   (vals->map i data1 data2)))]
    (is= result
      [{:i 0 :data1 [] :data2 [0 1 2]}
       {:i 1 :data1 [0] :data2 [1 2]}
       {:i 2 :data1 [0 1] :data2 [2]}
       {:i 3 :data1 [0 1 2] :data2 []}])))

So, we avoid the degenerate case where either data1 or data2 is the empty vector.

(defn partition-when
  [pred coll]
  (let [data       (vec coll)
        N          (count data)
        N-1        (dec N)
        ; We use `split-at` to partition the coll. Given a coll like [0 1 2], it makes
        ; no sense to give degenerate splits like {:data1 [] :data2 [0 1 2]}
        ; or {:data1 [0 1 2] :data2 []}. So, we need the split point in the range [1..(N-1)]
        split-idxs (loop [i    1
                          idxs []]
                     (if-not (<= i N-1)
                       idxs
                       (let [[data1 data2] (split-at i data)
                             split?      (pred data1 data2)
                             result-next (if split?
                                           (append idxs i)
                                           idxs)
                             i-next      (inc i)]
                         (recur i-next result-next))))
        ; Since we are using `subvec`, we must add in the "default" values at the
        ; start/end of the vector
        split-idxs (glue [0] split-idxs [N])
        idx-pairs  (partition 2 1 split-idxs)
        subvecs    (reduce (fn [cum [start end]]
                             (let [next-part (subvec data start end)
                                   next-cum  (append cum next-part)]
                               next-cum))
                     []
                     idx-pairs)]
    subvecs))

and the unit test. Notice the predicate function must take responsibility for pulling individual elements out of data1 and data2

(verify
  (let [split-fn (fn [data1 data2]
                   (let [x (last data1)
                         y (first data2)]
                     (< (inc x) y)))]
    (is= [[1 2 3] [8 9 10] [99]]
      (partition-when split-fn
        [1 2 3 8 9 10 99])))
  )

This function is now part of the Tupelo library.

I find this solution pretty concise:

(defn partition-contiguous [numbers]
  (->> numbers
       (partition-by identity)
       (map-indexed cons)
       (partition-by (fn [[x y]] (- x y)))
       (map #(mapcat rest %))))

(partition-contiguous [1 2 3 3 8 9 9 10 10 99])
;; => ((1 2 3 3) (8 9 9 10 10) (99))

The library dev.weavejester/medley ("A small collection of useful, mostly pure functions that might not look out of place in the clojure.core namespace") contains partition-between since 1.7.0. That function can be used to partition a sorted collection into contiguous partitions:

(require '[medley.core :refer [partition-between]])

(partition-between (fn [x y] (> y (inc x))) [1 2 3 8 9 10 99])
;; => ((1 2 3) (8 9 10) (99))