Section B.1 Python Iterators
All programming languages allow for looping. A common form of loop is one in which a series of instructions are executed for each value of some index variable, commonly for values between two integers. Python allows a bit more generality by having structures called “iterators” over which looping can be done. An iterator can be as simple as a list, such as
[0,1,2,3], but also can be a power set of a finite set, as we see below, or the keys in a dictionary, which is described in the next section.Subsection B.1.1 Counting Subsets
Suppose we want to count the number of subsets of \(\{0,1,2,...,9\}\) 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 all subsets will be 2 raised to the number of elements in \(U\text{,}\) which would be \(2^{10}=1024\text{,}\) but let’s check.
The validity check in this case is very simple. For each element, \(k\text{,}\) of a set, \(B\text{,}\) we ask whether its successor, \(k+1\text{,}\) 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 we try two tests, one with a valid set and one with an invalid one.
Finally we do the counting over our power set, incrementing the count variable with each valid set.
