Description

CSE 15: Discrete Mathematics Laboratory 4
• This lab assignment will be graded but its grade will NOT be counted towards computing the course grade.
• Start early.
Introduction
Python provides a datatype set that offers many of the the features we associate with mathematical sets. Sets in python have two important features identical to mathematical sets: they are unordered, and they cannot have duplicates.
The following lines show how to create a set starting from a list of elements:
>>> A = set([’a’,’b’,c’,’d’,’d’])
>>> print(A)
{’a’, ’c’, ’b’, ’d’}
Note that when you build the set the duplicate ’d’ character is removed, and when you print it the order is different from the one used in the input list. Another way to create a set is by enumerating the elements:
>>> B = {’dog’,’cat’,’tiger’}
>>> print(B)
{’tiger’, ’dog’, ’cat’}
Note once more that the elements in the set are printed in an order different from the one provided when creating the set. Given a set A and an element a we can use the in operator to determine if a∈A.
>>> ’tiger’ in A
False
>>> ’tiger’ in B
True
Another way to create a set is to to use a list of elements and then use the set constructor, like in the following example:
>>> list_of_chars = [’a’,’b’,’c’]
>>> S = set(list_of_chars)
>>> print(S)
{’b’, ’c’, ’a’}
You can use this approach to build the empty set:
>>> empty_set = set() >>> print(emtpy_set) set()
Python provides builtin operators for usual set operations like union (python operator |), intersection (python operator &), and difference (python operator -).
>>> print(A | B)
{’tiger’, ’a’, ’cat’, ’dog’, ’c’, ’b’}
>>> C = { ’cat’, ’lion’}
>>> print (B&C)
{’cat’} >>> print(A&C) set() >>> print(B-C)
{’dog’, ’tiger’}
Python also offers operators to work with subsets: < for (, <= for ⊆, > for ), and >= for ⊇.
>>> A < A
False
>>> A <= A
True
>>> D = {’dog’}
>>> D < B
True
The same operators can also be obtained using functions (see documentation below). Finally, the operator len is used to determine the number of elements in a set:
>>> len(A|B)
6
Since elements in a set are not ordered, there is no operator to access a specific element (e.g., you cannot access the third element or the last element in a set), but you can iterate through all elements in a set. >>> for element in A:
>>> print(element)
’a’
’c’
’b’
If you want to add or remove an element from a set, you can use the methods add or remove
>>> B.add(’rabbit’)
>>> print(B)
{’cat’, ’dog’, ’eagle’, ’rabbit’, ’tiger’}
>>> B.remove(’dog’)
>>> print(B)
{’tiger’, ’rabbit’, ’cat’, ’eagle’}
The type set in Python has however a notable difference from mathematical sets. A python set cannot be an element of another set. The specific reason go beyond what is covered in this course.
For a complete documentation of the set datatype, see https://docs.python.org/3/library/stdtypes. html#set. Before moving to the next section, you are encouraged to familiarize yourself with sets using the interactive python console.
1 Powersets
Write a program that reads the elements of a set from the keyboard, stores them in a set, and then determines its powerset. Specifically, the program should repeatedly ask the user:
Enter one more element ? [Y/N]
If the user answers Y then an new element is read from the keyboard:
Enter the new element in the set:
This cycle continues until the user answers N to the first question. At that point the program shall compute the powerset of the set of elements provided by the user, and print it to the screen. The powerset should not only be printed to the screen, but also stored in an instance of set.
Important: for what stated above, the elements of the powerset cannot be sets themselves. It is ok to store them in tuples. Note that while you can use a list to create a set (like in the example where we used list of chars), you cannot store lists in a set because of the same reason you cannot store sets inside a set. For example, the following code will give you an error
>>> A = [1,2]
>>> B = [3,4]
>>> C = [A,B]
>>> D = set(C)
—————————————————————————
TypeError Traceback (most recent call last)
<ipython-input-24-457b02ea603c> in <module> —-> 1 D = set(C)
TypeError: unhashable type: ’list’
The reason is that D = set(C) tries to build a set of elements from the list C, and the elements of C are the lists A and B. On the contrary, E = set(A) would be ok, because it builds a set from the elements of A, and the elements of A are integers.
2 Frozensets – optional
Python provides another datatype called frozenset that is similar to set but is immutable, i.e., its contents cannot change (no adding or removing, after it has been created). Instances of frozenset can be elements of a set (or also frozenset). Rewrite your solution using frozenset, and store the powerset in a set containing instances of frozenset. The documentation for https://docs.python.org/3/library/ stdtypes.html#set.
Of course you can find the solutions for the above questions on the Internet. But since this assignment does not count towards your final grade, your should really take the opportunity of challenges yourself and focus on learning something without stressing out for the grade.