从序列中的另一个列表中搜索列表（不一定是相同的顺序）

Question

我有一个列表说：

l1 = [0, 1, 2]

和

l2 = [2, 1, 0, 1, 3, 2]

我运行在l2上的一个算法并得到l1作为输出（我运行前缀扫描算法是一种顺序模式挖掘）。现在我的任务是识别它的反面，即）从 [0,1,2]，我必须识别 l2 是否具有该模式。

最初我通过计算 l1 的索引并进行比较来尝试索引部分，但它会失败，因为 1,2 甚至出现在 0 之前。

知道我们如何解决这个问题吗？

输入：

l1 = [0, 1, 2]
l2 = [2, 1, 0, 1, 3, 2]

期望的输出：

l2 contains l1 (since 0, 1, 2 is present in l2)

注意：虽然 2,1 甚至更早出现，但我们必须检查在 0 之后我们是否以任何方式看到 1,2

Answer 1

如果您只想检查 l1 中的元素是否是 l2

的子集

set(l1) <= set(l2)

Answer 2

如果顺序很重要，但连续性不重要，最简单的方法是按顺序查找每个元素：

searchidx = 0
try:
    for elem in l1:
        searchidx = l2.index(elem, searchidx) + 1
except ValueError:
    # ... action to take when not found
else:
    # ... action to take when found

list.index 在这里很有帮助，它让您在找到最后一个元素后立即恢复搜索，而无需切片或重新检查您已经搜索过的元素。

如果顺序无关紧要，只需将一个或两个输入转换为 sets（或 collections.Counter，如果一个或两个输入中可能存在重复项，并且必须考虑计数），并检查 l1 的 set 是否是 l2 的 set 的子集（或者反转它，如果 l2 是 [=16 的超集=]):

l1 = [0, 1, 2]
l2 = [2, 1, 0, 1, 3, 2]
s1 = set(l1)
s2 = set(l2)
if s1 <= s2:  # Or s1.issubset(l2) (or s2), or s2 >= s1, or s2.issuperset(l1) (or s1)
    print("l2 contains all the elements of l1")

从性能的角度来看，一次性测试最有效的方法可能是：

l1 = [0, 1, 2]
l2 = [2, 1, 0, 1, 3, 2]
if set(l1).issubset(l2):
    print("l2 contains all the elements of l1")

因为它最小化了临时 set 的大小，并且可以想象在不测试所有 l2 的情况下短路（取决于它的实现方式）。

Answer 3

自己看看difflib or implement a longest common subsequence算法。然后您可以检查 LCS 是否具有与最短序列相同的长度，比如 l1，从而得出结论它包含在 l2 中。

Answer 4

您的标题说顺序无关紧要，但您的描述暗示顺序确实重要，但元素不必是连续的。在后一种情况下，按顺序查找每个元素，在列表的其余部分继续搜索：

order = [0, 1, 2]
full = [2, 1, 0, 1, 3, 2]
part = full[:]

for val in order:
    if val in part:
        part = part[part.index(val)+1:]   # This is the step I think you're missing.
        print (val, "found", part)
    else:
        print("Sequencing failed")
        break

输出（带跟踪）：

0 found [1, 3, 2]
1 found [3, 2]
2 found []

Answer 5

不是最漂亮的，但我觉得这就是你想要的：

l1 = [0, 1, 2]

l2 = [2, 1, 0, 1, 3, 2]
l3 = [2, 1, 0, 4, 3]


def contains(arr, sequence):
    seq_index = 0
    for element in arr:
        try:
            if element == sequence[seq_index]:
                seq_index += 1
        except IndexError:
            break
    return seq_index == len(sequence)


assert contains(l2, l1)
assert not contains(l3, l1)

contains 将循环遍历给定的数组，每当它看到要查找的下一个项目时，就会进入序列中的下一个项目。然后它会 return True 如果它通过了整个序列。

从序列中的另一个列表中搜索列表（不一定是相同的顺序）

Search list from another list in a sequence(not necessarily same order)

python

list

sequence