Clojure: 如何测试一个序列是否是另一个序列的“子序列”

Question

在Clojure中，有没有一种简单/惯用的方法来测试一个给定序列是否包含在另一个序列中？类似于:

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

（其中 subseq？是一个理论函数，它可以执行我所描述的操作）

看起来在核心或其他Clojure库中没有这样的功能...假设这是真的，那么有相对简单的方法来实现这样的功能吗？

- Dave Yarwood

---

注意，核心中有一个subseq函数，但它可能不完全符合您的要求--http://clojuredocs.org/clojure_core/clojure.core/subseq - georgek

我看到了...那个函数完全是另一回事。 - Dave Yarwood

Answer 1

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

- amalloy

---

这里最常用的代码片段是 https://exercism.org/tracks/clojure/exercises/sublist/solutions - VP.

Answer 2

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

- A. Webb

---

这很好，但它将使用Java的相等概念而不是Clojure的。例如，(subseq [[1]] '((1)))将返回false而不是true。 - amalloy

Answer 3

***

免责声明编辑

由于评论部分中讨论的原因，本提案不可靠。

***

@amalloy的解决方案有一个缺陷 - 它无法处理无限惰性序列。因此，当您运行以下代码时，它将永远循环： (subseq? [1 2 3] (cycle [2 3 1])) 我提出了这个实现来修复这个问题：

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

- Damian Hryniewicz

---

你正在改进的解决方案是我的，不是Dave Yarwood的。而且这个改进也无效。如果你搜索任何有限子序列，你可能会错过针头，如果它发生在该子序列之外。例如，考虑(subseq? [1] [2 2 2 1])。我的解决方案并不高效，但这不是改进它的方法。此外，当被调用为(subseq? [1 2 3] (cycle [2 3 1]))时，它可以正常工作，所以我不确定你试图修复什么。 - amalloy

啊，你说得对。其实两件事都是。不幸的是，我无法恢复我今天早些时候遇到的错误。不管怎样，还是谢谢你的回复！ - Damian Hryniewicz

哦，是的，我找到问题了。当它找到解决方案时，它确实有效。但如果找不到解决方案，它将永远循环：(subseq? [1 2 3] (cycle [3 2 1]) - Damian Hryniewicz

也许结论是，在无限序列中搜索子序列并不明智 :) - Damian Hryniewicz

正确的解决方案会在给定不包含所搜索子序列的无限序列时永远不会终止。你只能得到“Yes”和“Maybe”的答案，永远不可能得到“No”。 - amalloy