How can I verify if one list is a subset of another

Question

I need to verify if a list is a subset of another - a boolean return is all I seek    Is testing equality on the smaller list after an intersection the fastest way to do this  Performance is of utmost importance given the number of datasets that need to be compared   Adding further facts based on discussions      Will either of the lists be the same for many tests   It does as one of them is a static lookup table  Does it need to be a list  It does not - the static lookup table can be anything that performs best  The dynamic one is a dict from which we extract the keys to perform a static lookup on         What would be the optimal solution given the scenario

User · Answer

Set theory is inappropriate for lists since duplicates will result in wrong answers using set theory.

For example:

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

has no meaning. Yes, it gives a false answer but this is not correct since set theory is just comparing: 1,3,5 versus 1,3,4,5. You must include all duplicates.

Instead you must count each occurrence of each item and do a greater than equal to check. This is not very expensive, because it is not using O(N^2) operations and does not require quick sort.

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

Then running this you get:

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

User · Answer

Here is how I know if one list is a subset of another one  the sequence matters to me in my case   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

User · Answer

Below code checks whether a given set is a  proper subset  of another set      def is proper subset set  superset        return all x in superset for x in set  and len set  lt len superset

User · Answer

Most of the solutions consider that the lists do not have duplicates  In case your lists do have duplicates you can try this   def isSubList subList mlist       uniqueElements set subList      for e in uniqueElements          if subList count e   gt  mlist count e               return False            It is sublist     return True   It ensures the sublist never has different elements than list or a greater amount of a common element   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

User · Answer

Pardon me if I am late to the party      To check if one set A is subset of set B  Python has A issubset B  and A  lt   B  It works on set only and works great BUT the complexity of internal implementation is unknown  Reference  https   docs python org 2 library sets html set-objects  I came up with an algorithm to check if list A is a subset of list B with following remarks    To reduce complexity of finding subset  I find it appropriate to sort both lists first before comparing elements to qualify for subset  It helped me to break the loop when value of element of second list B j  is greater than value of element of first list A i   last index j is used to start loop over list B where it last left off  It helps avoid starting comparisons from the start of list B  which is  as you might guess unnecessary  to start list B from index 0 in subsequent iterations   Complexity will be O n ln n  each for sorting both lists and O n  for checking for subset  O n ln n    O n ln n    O n    O n ln n   Code has lots of print statements to see what s going on at each iteration of the loop  These are meant for understanding only    Check if one list is subset of another list  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   gt  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   lt   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      Output   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

User · Answer

gt  gt  gt  a    1  3  5   gt  gt  gt  b    1  3  5  8   gt  gt  gt  c    3  5  9   gt  gt  gt  set a   lt   set b  True  gt  gt  gt  set c   lt   set b  False   gt  gt  gt  a     yes    no    hmm    gt  gt  gt  b     yes    no    hmm    well    gt  gt  gt  c     sorry    no    hmm    gt  gt  gt    gt  gt  gt  set a   lt   set b  True  gt  gt  gt  set c   lt   set b  False

User · Answer

one    1  2  3  two    9  8  5  3  2  1   set x in two for x in one     set  True     If list1 is in list 2     x in two for x in one  generates a list of True   when we do a set x in two for x in one  has only one element  True

User · Answer

The performant function Python provides for this is set issubset  It does have a few restrictions that make it unclear if it s the answer to your question  however   A list may contain items multiple times and has a specific order  A set does not  Additionally  sets only work on hashable objects    Are you asking about subset or subsequence  which means you ll want a string search algorithm   Will either of the lists be the same for many tests  What are the datatypes contained in the list  And for that matter  does it need to be a list    Your other post intersect a dict and list made the types clearer and did get a recommendation to use dictionary key views for their set-like functionality  In that case it was known to work because dictionary keys behave like a set  so much so that before we had sets in Python we used dictionaries   One wonders how the issue got less specific in three hours

User · Answer

One more solution would be to use a intersection   one    1  2  3  two    9  8  5  3  2  1   set one  intersection set two      set one    The intersection of the sets would contain of set one   OR   one    1  2  3  two    9  8  5  3  2  1   set one   amp   set two      set one

User · Answer

If you are asking if one list is  contained  in another list then    gt  gt  gt if listA in listB  return True   If you are asking if each element in listA has an equal number of matching elements in listB try   all True if listA count item   lt   listB count item  else False for item in listA

User · Answer

Since no one has considered comparing two strings  here s my proposal  You may of course want to check if the pipe   quot   quot   is not part of either lists and maybe chose automatically another char  but you got the idea  Using an empty string as separator is not a solution since the numbers can have several digits   12 3      1 23   def issublist l1 l2       return     join  str i  for i in l1   in     join  str i  for i in l2

User · Answer

Assuming the items are hashable   gt  gt  gt  from collections import Counter  gt  gt  gt  not Counter  1  2   - Counter  1   False  gt  gt  gt  not Counter  1  2   - Counter  1  2   True  gt  gt  gt  not Counter  1  2  2   - Counter  1  2   False   If you don t care about duplicate items eg   1  2  2  and  1  2  then just use    gt  gt  gt  set  1  2  2   issubset  1  2   True      Is testing equality on the smaller list after an intersection the fastest way to do this     issubset will be the fastest way to do it  Checking the length before testing issubset will not improve speed because you still have O N   M  items to iterate through and check

User · Answer

In python 3 5 you can do a   set    index  to get the element  It is much slower solution than other methods   one    1  2  3  two    9  8  5  3  2  1   result   set x in two for x in one     result  0     True   or just with len and set  len set a b      len set a

User · Answer

one    1  2  3  two    9  8  5  3  2  1   all x in two for x in one    Explanation  Generator creating booleans by looping through list one checking if that item is in list two   all   returns True if every item is truthy  else False    There is also an advantage that all return False on the first instance of a missing element rather than having to process every item

[python] How can I verify if one list is a subset of another?

Examples related to python

Examples related to list