Clojure: trouver des éléments séquentiels d'une séquence

Question

Dans un programme Clojure, j'ai une séquence de nombres:

(2 3 4 6 8 1)

Je veux trouver la sous-séquence la plus longue où les éléments sont séquentiels:

(2 3 4)

Je suppose que cela impliquera (take-while ...) ou (reduce ...).

Toutes les idées?

Précision : J'ai besoin la plus longue liste initiale des éléments séquentiels. Beaucoup plus facile, je suis sûr. Merci pour les solutions au problème plus difficile que je pose d'abord.

Answer 1

Si vous ne souhaitez que la séquence initiale plus longue, c'est un 1-liner:

(defn longest-initial-sequence [[x :as s]]
  (take-while identity (map #(#{%1} %2) s (iterate inc x))))

Answer 2

Compte tenu du commentaire de l'OP sur la question - qui change complètement le jeu! - cela peut être écrit très simplement:

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

Notez que c'est en fait paresseux. Je pense qu'il ne pas tenir sur la tête de doubletons grâce à la compensation des habitants. Une autre version:

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

La version originale de la question est plus amusant, bien! :-) Une solution super simple qui pourrait être construit en utilisant ce qui précède, mais bien sûr, ce serait nettement moins performant que l'utilisation reduce. Je vais voir si j'ai rien substantiellement différent de solutions de zmila et de dnolen - et pourtant encore assez performant - d'ajouter à cette partie de ce fil plus tard. (Pas très probable, je suppose.)

Answer 3

Réponse à l'original:

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

Une solution plus générique pour les personnes intéressées:

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

Je pense que cela est beaucoup mieux.

Answer 4

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