Coding examples
Following are some attempts at defining a function isSubset, which takes two arguments, a and b, and returns True if a is a subset of b, assuming that a and b are represented as lists of elements.
Here is one answer to the problem which is in the Pythonic functional style.
def isSubset(a, b):
return reduce(operator.and_, [x in b for x in a])
This is short and direct. The expression x in b tests to see if the item x is in the structure b. So, [x in b for x in a] is a list of Booleans, one for each components in a, indicating whether that component is in b. Finally, we replace that list using the and operator11 , which will have the value True if all of the elements of the list are False, and True otherwise.
An alternative is to do it recursively:
def isSubset(a, b):
if a == []:
return True
else:
return a[0] in b and isSubset(a[1:], b)
The base case of the recursion is that a is the empty list; in that type, it's define that a is a subset of b. Otherwise, we may give our answer in terms of isSubset, but asking a simpler question. So, we call that a is a subset of b if the ?rst element of a is a member of b and the set of rest of the elements of a is a subset of b.
We can go even farther in the recursive solution for compressing:
def isSubset(a, b):
return a == None or a[0] in b and isSubset(a[1:], b)
Here, we are taking advantage of the fact that in Python (and most other languages), the or Boolean operator has the "early out" charters tics. That is, if we are calculating e1 or e2, we start by evaluating e1, and if it is True, then we know the output of the expression has to be True, and therefore we give without calculating e2. So, or can perform as a kind of conditional operator. Some person would search this program too abstruse (shorter isn't always better), and some would take it very beautiful.
Here is another good solution, this time in the imperative style:
def isSubset(a, b):
for x in a:
if not x in b:
return False return True
It works by going through the component in a, in order. If any of those components is not in b, then we can immediately quit and give False. Otherwise, if we have taken through all of the components in a, and each of them has been in b, then a really is a subset of b and we may give True.
Here is another imperative program:
def isSubset(a, b): result = True for x in a:
result = result and x in b return result
This procedure starts by initializing a result to True, which is the check component for and (it plays the same role as 0 for add). Then it tends all the way through the structure a, and ands the last result with x in b. This calculation is as the computation done in the functional version, but rather than preparing the entire list of Booleans and then replacing, we inter leave the individual membership tests with combining them into a result.