如何验证一个列表是否是另一个列表的子集？

Question

我需要验证一个列表是否为另一个列表的子集 - 我只需要布尔值返回。在取交集后测试较小列表的相等性是否是最快的方法？考虑到需要比较的数据集数量，性能非常重要。 根据讨论添加进一步的事实: 1. 许多测试中两个列表中的任意一个是否相同？是的，其中一个是静态查找表。 2. 它需要是一个列表吗？不需要 - 静态查找表可以是任何表现最佳的东西。动态表是一个字典，我们从中提取键来执行静态查找。 在这种情况下，什么是最优解决方案？

- IUnknown

---

你提到速度，也许根据你的使用情况，numpy会很有用。 - ninMonkey

列表项是否可哈希？ - wim

如果顺序很重要，这可能是一个不错的起点 - StackOverflow - 在Python中确定一个序列是否在另一个序列中的最佳方法 - user764357

你需要真子集，还是可以相等？ - törzsmókus

为什么不将 list_a 转换为集合后使用 issubset() 方法来检查其是否是 list_b 的子集？ - SeF

Answer 1

>>> a = [1, 3, 5]
>>> b = [1, 3, 5, 8]
>>> c = [3, 5, 9]
>>> set(a) <= set(b)
True
>>> set(c) <= set(b)
False

>>> a = ['yes', 'no', 'hmm']
>>> b = ['yes', 'no', 'hmm', 'well']
>>> c = ['sorry', 'no', 'hmm']
>>> 
>>> set(a) <= set(b)
True
>>> set(c) <= set(b)
False

- Yulan Liu

---

这种方法看起来最简单易懂，但是最快的方法应该是使用set(a).issubset(b)，因为在这种情况下，你只将 a 转换为集合而不转换 b，从而节省时间。 你可以使用timeit比较这两个命令消耗的时间。例如：timeit.repeat('set(a)<set(b)', 'a = [1,3,5]; b = [1,3,5,7]', number=1000) 和 timeit.repeat('set(a).issubset(b)', 'a = [1,3,5]; b = [1,3,5,7]', number=1000)。 - Yulan Liu

很抱歉告诉你，但issubset的第一件事就是检查参数是否为set/frozenset，如果不是，它会将其转换为一个临时的set用于比较，然后运行检查，最后丢弃临时的set。时间差异（如果有的话）可能与LEGB查找成本（第二次查找set比现有set上的属性查找更昂贵）的小差异有关，但对于足够大的输入来说，这基本上是相同的。 - ShadowRanger

如果两个列表包含相同的值，那么这个条件语句会返回false，应该将条件改为set(a) <= set(b)，请注意不要改变原意。 - ssi-anik

这个答案怎么可能正确呢？他要求的是一个列表，而不是一个集合。它们完全不同。如果 a=[1, 3, 3, 5, 5]，b=[1, 3, 3, 3, 5]，那该怎么办？对于重复项，集合理论是不适用的。 - Eamonn Kenny

我还要指出，如果a=[1,3,5]和b=[1,3,5]，那么set(a) < set(b)将返回False。您可以添加等于运算符来处理这些情况：即set(a) <= set(b)。 - Jon

Answer 2

使用set.issubset

示例：

a = {1,2}
b = {1,2,3}
a.issubset(b) # True

a = {1,2,4}
b = {1,2,3}
a.issubset(b) # False

---

Python提供的高效函数是set.issubset。然而，它有一些限制使得不清楚它是否是你问题的答案。

列表可以包含多个相同项并具有特定顺序。集合没有。此外，集合只对可哈希对象有效。

你是在询问子集还是子序列（这意味着你需要一种字符串搜索算法）？两个列表中是否会有很多个测试？列表中包含的数据类型是什么？而且，它必须是一个列表吗？

您的另一篇文章澄清了类型，并获得了使用字典键视图作为其类似于集合功能的建议。在那种情况下，因为字典键行为类似于集合（在Python中没有集合之前我们使用字典），所以已知可以正常工作。人们想知道问题如何在三小时内变得不太具体。

- Yann Vernier

---

我只涉及一个子集，issubset表现得很好 - 谢谢。 然而，我对这里有两个问题很好奇。 1.这两个列表中的任何一个在多次测试中都会是相同的吗？ 是的，其中一个是静态查找表。 2.它需要成为列表吗？ 不需要-静态查找表可以是任何表现最佳的东西。 动态表是字典，我们从中提取键以执行静态查找。 这个事实会改变解决方案吗？ - IUnknown

并不多。字典的键是类似于集合的，并且已经排列在哈希表中，因此对于静态部分使用集合不会引起额外的复杂性。基本上，一个是字典的事实意味着您可能不需要将静态部分转换为集合（您可以使用O(n)性能检查all(itertools.imap(dict.has_key, mylist))）。 - Yann Vernier

我不明白为什么这个答案（或任何依赖集合的其他解决方案）能被接受。问题是关于列表的，我坦率地认为“验证一个列表是否是另一个列表的子集”中的子集并不应该被字面理解。将其转换为集合后，任何重复元素的信息都会丢失，然而，如果初始列表可能包含那些元素，则检查它们是否出现在第二个列表中也很重要，以确保一个列表的所有元素都可以在另一个列表中找到。但是集合无法做到这一点！ - inVader

上下文很重要；这被接受为帮助提问者并解释了区别。我们被告知候选人可以表示为集合，因此这是一个集合任务。你的情况可能不同，你提到的差异可以使用多重集合，如collections.Counter来解决。 - Yann Vernier

Answer 3

one = [1, 2, 3]
two = [9, 8, 5, 3, 2, 1]

all(x in two for x in one)

说明：该生成器通过循环遍历列表 one 并检查该项是否在列表 two 中，创建布尔值。如果每一项都为真，则 all()返回 True ，否则返回 False 。

all的另一个优点是，它在遇到缺失元素的第一个实例时返回False，而无需处理每个项。

- voidnologo

---

我认为为了可读性并明确你想实现什么，set(one).issubset(set(two)) 是一个很好的解决方案。使用我发布的解决方案，只要对象有适当定义的比较运算符，就可以将其应用于任何对象。 - voidnologo

使用生成器表达式而不是列表推导式；前者将允许all正确地进行短路，而后者将执行所有检查，即使从第一个检查中就可以清楚地知道测试会失败。只需删除方括号即可获得all(x in two for x in one)。 - ShadowRanger

我错了吗，或者你不能在本地使用这种方法？ - Homper

在保留顺序的情况下，我认为这是检查子集的最佳解决方案。 - ajskateboarder

Answer 4

假设这些项是可哈希的

>>> from collections import Counter
>>> not Counter([1, 2]) - Counter([1])
False
>>> not Counter([1, 2]) - Counter([1, 2])
True
>>> not Counter([1, 2, 2]) - Counter([1, 2])
False

如果您不关心重复项，例如 [1, 2, 2] 和 [1, 2]，那么只需使用：

>>> set([1, 2, 2]).issubset([1, 2])
True

测试交集后较小列表的等式是否是最快的方法？使用.issubset是最快的方式。在测试issubset之前检查长度不会提高速度，因为仍需要迭代并检查O(N + M)个项。

- jamylak

Answer 5

另一种解决方案是使用 intersection。

one = [1, 2, 3]
two = [9, 8, 5, 3, 2, 1]

set(one).intersection(set(two)) == set(one)

集合的交集包含了第一个集合

(或者)

one = [1, 2, 3]
two = [9, 8, 5, 3, 2, 1]

set(one) & (set(two)) == set(one)

- SuperNova

Answer 6

集合论对于列表来说是不适当的，因为使用集合论会导致重复项产生错误答案。

例如：

a = [1, 3, 3, 3, 5]
b = [1, 3, 3, 4, 5]
set(b) > set(a)

“没有意义”是错误的。是的，它会给出错误的答案，但这是不正确的，因为集合理论只是在比较：1、3、5与1、3、4、5。必须包括所有重复项。

相反，您必须计算每个项目的每个出现次数，并进行大于等于检查。这并不是非常昂贵，因为它不使用O(N^2)操作，也不需要快速排序。

#!/usr/bin/env python

from collections import Counter

def containedInFirst(a, b):
  a_count = Counter(a)
  b_count = Counter(b)
  for key in b_count:
    if a_count.has_key(key) == False:
      return False
    if b_count[key] > a_count[key]:
      return False
  return True


a = [1, 3, 3, 3, 5]
b = [1, 3, 3, 4, 5]
print "b in a: ", containedInFirst(a, b)

a = [1, 3, 3, 3, 4, 4, 5]
b = [1, 3, 3, 4, 5]
print "b in a: ", containedInFirst(a, b)

然后运行此命令，您将获得以下结果：

$ python contained.py 
b in a:  False
b in a:  True

- Eamonn Kenny

Answer 7

one = [1, 2, 3]
two = [9, 8, 5, 3, 2, 1]

set(x in two for x in one) == set([True])

如果 list1 在 list2 中:

• (x in one for x in two) 生成一个由True组成的列表。

• 当我们执行 set(x in one for x in two)时，只有一个元素（True）。

- SuperNova

Answer 8

在Python 3.5中，你可以使用[*set()][index]来获取元素。这种方法比其他方法要慢得多。

one = [1, 2, 3]
two = [9, 8, 5, 3, 2, 1]

result = set(x in two for x in one)

[*result][0] == True

或者只使用len和set函数

len(set(a+b)) == len(set(a))

- SuperNova

Answer 9

以下代码检查给定的集合是否是另一个集合的“真子集”

 def is_proper_subset(set, superset):
     return all(x in superset for x in set) and len(set)<len(superset)

- Leo Bastin

---

为什么你认为空集打破了已经建立的数学规则是理想的呢？维基百科：空集 { }，用符号 ∅ 表示，也是任何给定集合 X 的子集。它始终是任何集合的真子集，除了自身。 - Yann Vernier

谢谢@YannVernier，我已经修改了代码以包括对子集和超集的空检查，因此当两者都为空时它会返回false。 - Leo Bastin

但是，你为什么要这样做呢？A是B的子集意味着A不包含B中没有的任何项，或者等价地说，A中的所有项也都在B中。因此，空集是所有集合的子集，包括它自己。你的额外检查断言它不是，而你声称这在某种程度上是理想的，但这与已有的术语相矛盾。这样做有什么好处呢？ - Yann Vernier

感谢@YannVernier，现在代码检查给定的集合是否为另一个集合的“真子集”。 - Leo Bastin

这和依赖于使用“集合”的答案一样糟糕。虽然从数学上讲，集合是不同元素的集合，但我们不能也不应该依赖这种假设来检查一个列表是否是另一个列表的一部分。如果初始列表包含重复项，则即使所询问的元素仅在第二个列表中出现一次，您的函数仍可能返回True。我认为这不是比较列表时正确的行为。 - inVader

Answer 10

大多数解决方案都认为列表中没有重复项。如果您的列表中有重复项，可以尝试以下方法：

def isSubList(subList,mlist):
    uniqueElements=set(subList)
    for e in uniqueElements:
        if subList.count(e) > mlist.count(e):
            return False     
    # It is sublist
    return True

它确保子列表永远不会有与列表不同的元素或更多的共同元素。

lst=[1,2,2,3,4]
sl1=[2,2,3]
sl2=[2,2,2]
sl3=[2,5]

print(isSubList(sl1,lst)) # True
print(isSubList(sl2,lst)) # False
print(isSubList(sl3,lst)) # False

- Ignacio Alorre