Python – validation一个列表是否是另一个列表的子集

我需要validation一个列表是否是另一个列表的子集 – 布尔返回就是我所寻求的。
在一个十字路口之后在小列表上testing平等是否是最快的方法？
考虑到需要比较的数据集的数量，性能是最重要的。
根据讨论添加更多事实：

1. 这两个列表中的任何一个对于许多testing都是一样的吗？
   这是因为其中一个是静态查找表
2. 它需要成为一个清单吗？
   它不 – 静态查找表可以是任何性能最好的。
   dynamic的是一个字典，我们从中提取键来执行静态查找。

考虑到这种情况，最佳解决scheme是什么？

Answer 1

Python为此提供的性能函数是set.issubset 。 但是，它有一些限制，使得它不清楚是否是你的问题的答案。

一个列表可能包含多个项目，并具有特定的顺序。 一套没有。 为了实现高性能，只能在可哈希对象上工作。

你问的子集或子序列（这意味着你会想要一个stringsearchalgorithm）？ 这两个列表中的任何一个对于许多testing都是一样的吗？ 列表中包含的数据types是什么？ 而就此而言，它是否需要成为一个清单？

你的其他职位相交字典和列表使得types更清晰，并得到了build议，使用字典的关键视图为他们的集样function。 在这种情况下，它是已知的工作，因为字典键行为像一个集（太多，以至于我们在Python设置之前，我们使用字典）。 人们不禁要问，在三个小时之内，这个问题的具体情况如何？

Answer 2

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

Answer 3

 one = [1, 2, 3] two = [9, 8, 5, 3, 2, 1] all(x in two for x in one) 

说明：生成器通过循环检查列表two是否在列表two检查是否创build布尔值。 如果每个项目都是真的，则all()返回True ，否则返回False 。

还有一个优点，就是在缺less元素的情况下首先返回False，而不必处理每个项目。

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 

在一个十字路口之后在小列表上testing平等是否是最快的方法？

.issubset将是最快的方法。 在testingissubset之前检查长度不会提高速度，因为您仍然有O（N + M）个项目要遍历和检查。

Answer 5

尝试按位与

 >>> set([1,2]) & set([1,2,3]) set([1, 2]) >>> set([0]) & set([1,2,3]) set([]) 

还没有分析它。

Answer 6

 one = [1, 2, 3] two = [9, 8, 5, 3, 2, 1] set(x in two for x in one) == set([True]) 

如果list1在列表2中：

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

• 当我们做一个set(x in two for x in one)只有一个元素（真）。

Answer 7

根据集合理论，如果子集和超集是空的，理想情况下应该返回False。 下面的代码是相应的。

  def isSubSet(superset, subset): return all(x in superset for x in subset) and len(subset)>0 and len(superset)>0 

Answer 8

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

例如：

 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）操作，不需要快速sorting。

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

Answer 9

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

 >>>if listA in listB: return True 

如果询问listA中的每个元素是否具有相同数量的listB中的匹配元素，请尝试：

 all(True if listA.count(item) <= listB.count(item) else False for item in listA) 

Answer 10

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

为了检查一个set A是set B子set B ， Python有A.issubset(B)和A <= B 它只能在set工作，而且工作的很好， 但内部实现的复杂性是未知的。 参考： https ： //docs.python.org/2/library/sets.html#set-objects

我想出了一个algorithm来检查list A是否是list B一个子集，并附带以下注释。

• 为了减less查找子集的复杂性，我发现在比较元素之前首先sort两个列表进行sort以适合子集合是合适的。
• 当第二个列表B[j]的元素的值大于第一个列表A[i]的元素的值时，它帮助我break了loop 。
• last_index_j被用来开始在list B上loop地方。 它有助于避免从list B的开始处开始比较（也就是说，您可能会认为不需要，从后续iterations index 0开始list B ）。

• 为了检查子集，将O(n)和O(n)分别sorting为O(n ln n) 。
  O(n ln n) + O(n ln n) + O(n) = O(n ln n) 。

• 代码有很多的print语句来看loop每次iteration发生了什么。 这些只是为了理解。

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

 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