CODEWITHSUNDEEP
clojuresequencesequencesseq
Dave Yarwood
Dave Yarwood

Reputation: 3010

Clojure: how to test if a seq is a "subseq" of another seq

Is there an easy / idiomatic way in Clojure to test whether a given sequence is included within another sequence? Something like:

(subseq? [4 5 6] (range 10))  ;=> true
(subseq? [4 6 5] (range 10))  ;=> false
(subseq? "hound" "greyhound") ;=> true

(where subseq? is a theoretical function that would do what I'm describing)

It seems that there is no such function in the core or other Clojure libraries... assuming that's true, is there a relatively simple way to implement such a function?

Upvotes: 5

Views: 1038

Answers (3)

Damian Hryniewicz
Damian Hryniewicz

Reputation: 86

***

DISCLAIMER EDIT

This proposal is not reliable for reasons discussed in comments section.

***

@amalloy 's solution has one flaw - it won't work with infinite lazy sequences. So it will loop forever when you run this: (subseq? [1 2 3] (cycle [2 3 1]))

I propose this implementation to fix this:

(defn- safe-b
  "In case b is a cycle, take only two full cycles -1 of a-count
  to prevent infinite loops yet still guarantee finding potential solution."
  [b a-count]
  (take
    (* 2 a-count)
    b))

(defn subseq? [a b]
  (let [a-count (count a)]
    (some #{a} (partition a-count 1 (safe-b b a-count)))))

=> #'user/safe-b
=> #'user/subseq?

(subseq? [1 2 3] (cycle [2 3 1]))
=> [1 2 3]
(subseq? [1 2 3] (cycle [3 2 1]))
=> nil
(subseq? [1 2 3] [2 3])
=> nil
(subseq? [2 3] [1 2 3])
=> [2 3]

Upvotes: -1

amalloy
amalloy

Reputation: 92077

(defn subseq? [a b]
  (some #{a} (partition (count a) 1 b)))

Upvotes: 12

A. Webb
A. Webb

Reputation: 26446

(defn subseq? [target source] 
  (pos? (java.util.Collections/indexOfSubList (seq source) (seq target))))

Upvotes: 2

Related Questions