Clojure: нахождение последовательных объектов от последовательности
В программе Clojure у меня есть последовательность чисел:
(2 3 4 6 8 1)
Я хочу найти самую длинную подпоследовательность, где объекты последовательны:
(2 3 4)
Я предполагаю, что это включит (take-while ...) или (reduce ...).
Какие-либо идеи?
Разъяснение: Мне нужен самый длинный первоначальный список последовательных объектов. Намного легче, я уверен. Спасибо за решения более трудной проблемы я первоначально позировал.
4 ответа
Если вас интересует только самая длинная начальная последовательность, то это 1-линейка:
(defn longest-initial-sequence [[x :as s]]
(take-while identity (map #(#{%1} %2) s (iterate inc x))))
Принимая во внимание комментарий ОП к вопросу - это полностью меняет игру! - это можно записать очень просто:
(let [doubletons (partition 2 1 [1 2 3 5 6])
increment? (fn increment? [[x y]]
(== (inc x) y))]
(cons (ffirst doubletons)
(map second (take-while increment? doubletons))))
;; returns (1 2 3)
Обратите внимание, что это на самом деле ленивый. Я ожидаю, что он не удержит голову дублетонов благодаря расчистке местных жителей.Другая версия:
(cons (first [1 2 3 5 6])
(map second (take-while increment? (partition 2 1 [1 2 3 5 6]))))
Однако исходная версия вопроса более интересна! :-) Сверхпростое решение этой проблемы можно было бы построить, используя вышеизложенное, но, конечно, это будет значительно менее производительно, чем использование reduce . Я посмотрю, есть ли у меня что-то существенно отличающееся от решений zmila и dnolen - и все же достаточно производительное - чтобы добавить к этой части этой темы позже. (Думаю, маловероятно.)
Ответ на оригинал:
(defn conj-if-sequential
([] [])
([a] a)
([a b] (let [a (if (vector? a) a [a])]
(if (= (inc (last a)) b)
(conj a b)
a))))
(reduce conj-if-sequential [2 3 4 6 8 1])
Более общее решение для заинтересованных:
(defn sequential-seqs
([] [])
([a] a)
([a b] (let [n (last (last a))]
(if (and n (= (inc n) b))
(update-in a [(dec (count a))] conj b)
(conj a [b])))))
(defn largest
([] nil)
([a] a)
([a b] (if (> (count b) (count a)) b a)))
(reduce largest (reduce sequential-seqs [] [2 3 4 6 8 1 4 5 6 7 8 9 13]))
Думаю, это намного лучше.
(defn find-max-seq [lst]
(let [[f & r] lst,
longest-seq (fn [a b] (if (> (count a) (count b)) a b)),
[last-seq max-seq] (reduce
(fn [ [[prev-num & _ :as cur-seq] max-seq] cur-num ]
(if (== (inc prev-num) cur-num)
[(conj cur-seq cur-num) max-seq]
[(list cur-num) (longest-seq cur-seq max-seq)]
))
[(list f) ()]
r)]
(reverse (longest-seq last-seq max-seq))))
(find-max-seq '(2 3 4 6 8 1)) ; ==> (2 3 4)
(find-max-seq '(3 2 3 4 6 8 9 10 11)) ; ==> (8 9 10 11)