Suppose we want to count the number of subsets of that contain no adjacent elements. First, we will define our universe and its power set. The plan will be to define a function that determines whether a subset is “valid” in the sense that it contains no adjacent elements. Then we will iterate over the subsets, counting the valid ones.
We know that the number of subsets will be 2 raised to the number of elements in , which would be , but let’s check.
The validity check in this case is very simple. For each element, , of a set, , we ask whether its successor, , is also in the set. If we never get an answer of “True” then we consider the set valid. This function could be edited to define validity in other ways to answer different counting questions.
It’s always a good idea to test your functions, so here is a list of two tests, one of a valid set and one of an invalid one.
Finally we do the counting over our power set, incrementing the count variable with each valid set.
Consider the following
As an afterthough, we might add the information that a raspberry is red as follows. You have to be careful in that if ‘Red’ isn’t already in the dictionary, it doesn’t have a value. This is why we need an if statement.