CODEWITHSUNDEEP
pythonsetsubsetmultisetmultiplicity
Joe Flip
Joe Flip

Reputation: 1195

Test if set is a subset, considering the number (multiplicity) of each element in the set

I know I can test if set1 is a subset of set2 with:

{'a','b','c'} <= {'a','b','c','d','e'} # True

But the following is also True:

{'a','a','b','c'} <= {'a','b','c','d','e'} # True

How do I have it consider the number of times an element in the set occurs so that:

{'a','b','c'}     <= {'a','b','c','d','e'}      # True
{'a','a','b','c'} <= {'a','b','c','d','e'}      # False since 'a' is in set1 twice but set2 only once
{'a','a','b','c'} <= {'a','a','b','c','d','e'}  # True because both sets have two 'a' elements

I know I could do something like:

A, B, C = ['a','a','b','c'], ['a','b','c','d','e'], ['a','a','b','c','d','e']
all([A.count(i) == B.count(i) for i in A]) # False
all([A.count(i) == C.count(i) for i in A]) # True

But I was wondering if there was something more succinct like set(A).issubset(B,count=True) or a way to stay from list comprehensions. Thanks!

Upvotes: 5

Views: 5965

Answers (5)

A. Rodas
A. Rodas

Reputation: 20679

Since Python 3.10, "Counters support rich comparison operators for equality, subset, and superset":

def issubset(X, Y):
    return Counter(X) <= Counter(Y)

Old: As stated in the comments, a possible solution using Counter:

from collections import Counter

def issubset(X, Y):
    return len(Counter(X)-Counter(Y)) == 0

Upvotes: 13

Kasper Dokter
Kasper Dokter

Reputation: 65

For those that are interested in the usual notion of multiset inclusion, the easiest way to test for multiset inclusion is to use intersection of multisets:

from collections import Counter

def issubset(X, Y):
    return X & Y == X

issubset(Counter("ab"), Counter("aab"))  # returns True
issubset(Counter("abc"), Counter("aab")) # returns False

This is a standard idea used in idempotent semirings.

Upvotes: 0

YvesgereY
YvesgereY

Reputation: 3888

Combining previous answers gives a solution which is as clean and fast as possible:

def issubset(X, Y):
    return all(v <= Y[k] for k, v in X.items())
  • No instances created instead of 3 in @A.Rodas version (both arguments must already be of type Counter, since this is the Pythonic way to handle multisets).
  • Early return (short-circuit) as soon as predicate is falsified.

Upvotes: 1

Abhijit
Abhijit

Reputation: 63707

As @DSM deleted his solution , I will take the opportunity to provide a prototype based on which you can expand

>>> class Multi_set(Counter):
    def __le__(self, rhs):
        return all(v == rhs[k] for k,v in self.items())


>>> Multi_set(['a','b','c']) <= Multi_set(['a','b','c','d','e'])
True
>>> Multi_set(['a','a','b','c']) <= Multi_set(['a','b','c','d','e'])
False
>>> Multi_set(['a','a','b','c']) <= Multi_set(['a','a','b','c','d','e'])
True
>>>

Upvotes: 1

lea
lea

Reputation: 418

The short answer to your question is there is no set operation that does this, because the definition of a set does not provide those operations. IE defining the functionality you're looking for would make the data type not a set.

Sets by definition have unique, unordered, members:

>>> print {'a', 'a', 'b', 'c'}
set(['a', 'c', 'b'])
>>> {'a', 'a', 'b', 'c'} == {'a', 'b', 'c'}
True

Upvotes: 3

Related Questions