longest contiguous increasing subsequence

[braver]

I'd like to partition a positive numeric sequence into subsequences so
that each increasing subsequence is the longest possible among its
neighbors. Here's the closest I got so far:

(use 'clojure.contrib.seq-utils)
(defn clis [s] (->> s (into [-1]) (partition 2 1) (partition-by (fn
[[x y]] (< x y))) (map #(map second %))))

-1 here plays the role of minus infinity. Prepending it with into
assumes we supply the original sequence as a vector; would be nice to
relax that and allow either a seq or a vector. Here's a sample
output:

(clis [3 2 1 2 3 0 1 2 3 4 0 1 1 2])
=> ((3) (2 1) (2 3) (0) (1 2 3 4) (0) (1) (1) (2))

In between decreasing and increasing, it assigns the middle element
wrongly. Reassigning it via an elaborate (partition 2 ...) with
regluing between halves seems too heavy... Anything smarter?

Cheers,
Alexy

[Meikel Brandmeyer]

Hi,

lazy-seq to the rescue:

user=> (defn clis
[coll]
(letfn [(step
[prev s]
(let [fst (first s)
lst (peek prev)]
(if (or (nil? s) (and lst (<= fst lst)))
(cons prev (clis s))
(recur (conj prev fst) (next s)))))]
(lazy-seq
(when-let [s (seq coll)]
(step [] s)))))

user=> (clis [3 2 1 2 3 0 1 2 3 4 0 1 1 2])
([3] [2] [1 2 3] [0 1 2 3 4] [0 1] [1 2])

Hope this helps.

Sincerely
Meikel

[carlitos]

On Jan 28, 7:26 am, braver <delivera...@gmail.com> wrote:

How about this? (not as smart as the other solution proposed, but
hopefully straightforward to understand)

(defn clis [coll]
(if (empty? coll) []
(loop [[head & tail] (rest coll) streak [(first coll)] output
[]]
(cond
(nil? head) (conj output streak)
(> head (peek streak)) (recur tail (conj streak
head) output)
true (recur tail [head] (conj
output streak))))))

Cheers,

Carlos

[carlitos]

;; Ok, I'll try again using less columns...

[braver]

Meikel -- cool lazy solution, but doesn't generalize to replace <=
with a predicate. Here's my non-lazy, reduce-based one generic with
instantiations:

(defn clis-pred
[pred s]
(let [[x & xs] s [r zs _]
(reduce (fn [[r zs z] e]
(if (pred z e) [r (conj zs e) e] [(conj r zs) [e] e]))
[[] [x] x] xs)] (conj r zs)))

(def clis-incr (partial clis-pred <))
(def clis-nondecr (partial clis-pred <=))
(def clis-nonincr (partial clis-pred >=))
(def clis-decr (partial clis-pred >))

Cheers,
Alexy

[carlitos]

If your input is a vector, the following will do the trick (relies on
subvec):

(use 'clojure.contrib.seq-utils)
(defn clis-pred [pred vec]
(->> vec
(partition 2 1)
(map reverse)
(map (partial reduce pred))
(cons false)
(positions false?)
(partition-all 2 1)
(map (partial apply subvec vec))))

In the general case, partition-by can be used:

(use 'clojure.contrib.seq-utils)
(defn clis-pred [pred seq]
(->> seq
(partition 2 1)
(reductions (fn [id [prev curr]] (if (pred curr prev) id (+ id
1))) 0)
(map vector seq)
(partition-by second)
(map (partial map first))))

Cheers,

Carlos