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

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 doesn't respect the order. Any function in Enum also wouldn't respect the order, and I cannot find anything in List.

Answer 1

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

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

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

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

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

Answer 2

最后这是我使用的实现：

  @spec list_contains_in_order(List.t(), List.t()) :: boolean
  def list_contains_in_order([], _), do: false

  def list_contains_in_order(container, contained) do
    if List.starts_with?(container, contained) do
      true
    else
      list_contains_in_order(tl(container), contained)
    end
  end

一种可能的性能优化是跟踪 container 的长度（不是通过检查每次迭代的长度，而是通过计算初始长度并在每次迭代中减少它）并与contained 的长度，所以一旦 container 变小我们就可以停止。

出于我的代码的目的（我们不希望列表很大），我将其保留为这样。

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

List contains another list in the same order

elixir