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

我需要验证一个列表是否是另一个列表的子集-布尔返回是我所寻求的。

在交叉路口后的小列表上测试相等性是最快的方法吗?考虑到需要比较的数据集的数量，性能是极其重要的。

在讨论的基础上补充进一步的事实:

  1. 对于许多测试，这两个列表是否都是相同的?其中一个是静态查找表。

  2. 需要是一个列表吗?它不是——静态查找表可以是任何性能最好的表。动态的是一个字典，我们从中提取键来执行静态查找。

在这种情况下，最佳解决方案是什么?

294117 次浏览
小开

假设项是可哈希的

>>> 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)个项要遍历和检查。

小开
最佳答案

使用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。然而，它确实有一些限制，不清楚它是否能回答你的问题。

一个列表可以多次包含项目，并具有特定的顺序。而一组则不是。此外，set只适用于hashable对象。

您是在询问子集还是子序列(这意味着您将需要字符串搜索算法)?对于许多测试，这两个列表是否都是相同的?列表中包含哪些数据类型?就此而言，它需要是一个列表吗?

你的另一篇文章将字典和列表相交使类型更清晰，并建议使用字典键视图来实现类似集的功能。在这种情况下，它是可以工作的，因为字典键的行为类似于集合(以至于在Python中有集合之前，我们使用字典)。人们不禁要问，为什么这个问题在三个小时内变得不那么具体了。

小开 
>>> 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
小开

如果你在问一个列表是否“包含”在另一个列表中，那么:

>>>if listA in listB: return True

如果你想知道listA中的每个元素在listB中是否有相等数量的匹配元素，试试:

all(True if listA.count(item) <= listB.count(item) else False for item in listA)
小开 
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，而不必处理每个元素。

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


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

如果list1在list 2中:

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

  • set(x in two for x in one)只有一个元素(True)。

小开

如果我迟到了，请原谅。；）

要检查set A是否是set B的子集，Python有A.issubset(B)和A <= B。它只能在set上工作，并且工作得很好。参考:https://docs.python.org/2/library/sets.html#set-objects

我提出了一个算法来检查list A是否是list B的子集，带有以下注释。

  • 为了降低查找子集的复杂性，我认为它适合于 sort在比较符合条件的元素之前先列出 李子集。< / >
  • 当第二个列表B[j]的元素值大于第一个列表A[i]的元素值时，它帮助我break loop。
  • last_index_j用于从list B上开始loop。这有助于避免从一开始就进行比较 list B(你可能会猜到这是不必要的，在随后的iterations中从index 0开始list B .)

  • 复杂度将为O(n ln n)，分别用于排序两个列表，O(n)用于检查子集 李O(n ln n) + O(n ln n) + O(n) = O(n ln n) . < / p > < / >

  • Code有很多print语句来查看loop的每个iteration处发生了什么。这些是用来理解的 李。< / p > < / >

检查一个列表是否是另一个列表的子集

is_subset = True;


A = [9, 3, 11, 1, 7, 2];
B = [11, 4, 6, 2, 15, 1, 9, 8, 5, 3];


print(A, B);


# skip checking if list A has elements more than list B
if len(A) > len(B):
is_subset = False;
else:
# complexity of sorting using quicksort or merge sort: O(n ln n)
# use best sorting algorithm available to minimize complexity
A.sort();
B.sort();


print(A, B);


# complexity: O(n^2)
# for a in A:
#   if a not in B:
#       is_subset = False;
#       break;


# complexity: O(n)
is_found = False;
last_index_j = 0;


for i in range(len(A)):
for j in range(last_index_j, len(B)):
is_found = False;


print("i=" + str(i) + ", j=" + str(j) + ", " + str(A[i]) + "==" + str(B[j]) + "?");


if B[j] <= A[i]:
if A[i] == B[j]:
is_found = True;
last_index_j = j;
else:
is_found = False;
break;


if is_found:
print("Found: " + str(A[i]));
last_index_j = last_index_j + 1;
break;
else:
print("Not found: " + str(A[i]));


if is_found == False:
is_subset = False;
break;


print("subset") if is_subset else print("not subset");

输出

[9, 3, 11, 1, 7, 2] [11, 4, 6, 2, 15, 1, 9, 8, 5, 3]
[1, 2, 3, 7, 9, 11] [1, 2, 3, 4, 5, 6, 8, 9, 11, 15]
i=0, j=0, 1==1?
Found: 1
i=1, j=1, 2==1?
Not found: 2
i=1, j=2, 2==2?
Found: 2
i=2, j=3, 3==3?
Found: 3
i=3, j=4, 7==4?
Not found: 7
i=3, j=5, 7==5?
Not found: 7
i=3, j=6, 7==6?
Not found: 7
i=3, j=7, 7==8?
not subset
小开

下面的代码检查一个给定的集合是否是另一个集合的“适当子集”

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

集合理论不适用于列表，因为重复使用集合理论会导致错误的答案。

例如:

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²)操作，也不需要快速排序。

#!/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
小开

在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))
小开

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

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


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

集合的交集将包含set one

(或)

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


set(one) & (set(two)) == set(one)
小开

下面是我如何知道如果一个列表是另一个列表的子集，在我的情况下，序列对我很重要。

def is_subset(list_long,list_short):
short_length = len(list_short)
subset_list = []
for i in range(len(list_long)-short_length+1):
subset_list.append(list_long[i:i+short_length])
if list_short in subset_list:
return True
else: return False
小开

大多数解决方案都认为列表没有副本。如果你的列表确实有重复，你可以试试这个:

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

它确保子列表的元素永远不会与list不同，或者公共元素的数量更多。

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
小开

由于没有人考虑比较两个字符串，下面是我的建议。

当然，您可能想检查管道("|")是否不属于这两个列表，可能会自动选择另一个char，但您已经明白了。

使用空字符串作为分隔符不是一个解决方案，因为数字可以有几个数字([12,3]!= [1,23])

def issublist(l1,l2):
return '|'.join([str(i) for i in l1]) in '|'.join([str(i) for i in l2])

提交答案