elixir - 列表包含另一个顺序相同的列表

Question

检查一个列表是否包含另一个列表的元素以相同顺序的长生不老方法是什么？一些测试来获得这个想法:

assert some_contains_function?([1, 2, 3], [1, 2])
assert some_contains_function?([3, 1, 2], [1, 2])
assert some_contains_function?([1, 2, 3], [2, 3])

refute some_contains_function?([1, 3, 2], [1, 2])
refute some_contains_function?([1, 2, 3], [1, 2, 4])

Kernel.--/2不尊重秩序。 Enum 中的任意函数也不会遵守订单，我在 List 中找不到任何东西.

Answer 1

有趣的问题。我也无法在执行此操作的标准库中找到好的函数。这似乎是一个与查找子字符串类似的问题，所以我认为查看 Elixir 如何实现查找子字符串可能会有用。事实证明，它使用了 Erlang 实现 written in C ，它使用 Boyer-Moore string-search algorithm .

因此，如果没有现有的实现，这是一个复杂的计算机科学问题。我设法编写了一个通过测试的版本，但我相信还有更好的实现!我认为您还应该通过实现回答您自己的问题。这听起来像是值得添加到标准库中的东西。也许这种算法很难在不可变语言中有效地实现？

无论如何，这是我得到的:

1. 构建一个 match 变量，我们将使用它来检查我们是否找到了子列表。
2. 遍历输入列表，将每个新元素推送到 match 变量。
3. 一旦 match 的长度与目标子列表的长度相同，每次我们将一个元素推到开头时，从末尾删除一个元素。
4. 如果在任何时候 match 等于目标子列表，我们就找到了匹配项。
5. 当我们用尽所有元素时，我们知道没有匹配项。

---

defmodule Lists do
  def contains_sublist?(list, sublist) do
    contains_sublist?(list, Enum.reverse(sublist), [])
  end

  defp contains_sublist?(_, sublist, sublist), do: true
  defp contains_sublist?([], _, _), do: false

  defp contains_sublist?([current | rest], sublist, match)
       when length(sublist) == length(match) do
    contains_sublist?(rest, sublist, [current | Enum.take(match, length(match) - 1)])
  end

  defp contains_sublist?([current | rest], sublist, match) do
    contains_sublist?(rest, sublist, [current | match])
  end

  def test do
    contains_sublist?([1, 2, 3], [1, 2]) &&
      contains_sublist?([3, 1, 2], [1, 2]) &&
      contains_sublist?([1, 2, 3], [2, 3]) &&
      !contains_sublist?([1, 3, 2], [1, 2]) &&
      !contains_sublist?([1, 2, 3], [1, 2, 4])
  end
end

测试:

iex(1)> Lists.test                                                                                            
true

---

它通过了所有测试，但由于它每次迭代都会遍历 match 列表，我怀疑对于大型子列表或大型输入列表，性能会降低，因为它是 O(m· n).