Clojure: поиск последовательных элементов из последовательности - PullRequest
Новая
       32

Clojure: поиск последовательных элементов из последовательности

6 голосов
/ 27 апреля 2010

В программе Clojure у меня есть последовательность чисел: 

(2 3 4 6 8 1)

Я хочу найти самую длинную подпоследовательность, в которой элементы являются последовательными: 

(2 3 4)

Я предполагаю, что это будет включать (take-while ...) или (reduce ...).

Есть идеи?

Уточнение : Мне нужен самый длинный начальный список последовательных предметов. Гораздо проще, я уверен. Спасибо за решение более сложной проблемы, которую я изначально поставил.

Ответы [ 4 ]

12 голосов
/ 27 апреля 2010

Если вас интересует только самая длинная начальная последовательность, это 1 строка: 

(defn longest-initial-sequence [[x :as s]]
  (take-while identity (map #(#{%1} %2) s (iterate inc x))))
5 голосов
/ 27 апреля 2010

Принимая во внимание комментарий ОП по вопросу - который полностью меняет игру! - это можно написать очень просто: 

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

Обратите внимание, что это на самом деле ленивый. Я ожидаю, что это не будет держаться за голову doubletons благодаря очистке местных жителей. Другая версия: 

(cons (first [1 2 3 5 6])
      (map second (take-while increment? (partition 2 1 [1 2 3 5 6]))))

Оригинальная версия вопроса более веселая! :-) Сверхпростое решение для этого может быть построено с использованием вышеупомянутого, но, конечно, это будет значительно менее производительным, чем использование reduce. Я посмотрю, есть ли у меня что-нибудь существенно отличающееся от решений Змилы и Днолена - и все же достаточно эффективное - чтобы добавить к этой части этой темы позже. (Не очень вероятно, я думаю.)

4 голосов
/ 27 апреля 2010

Ответ оригиналу: 

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

Я думаю, что это намного лучше.

2 голосов
/ 27 апреля 2010 
(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)
...