Tuples and Sets

Tuples

In Python (and also Mathematics) a tuple is a finite ordered list of objects. If \(n \geq 1\) is an integer, a \(n\)-tuple is an ordered list of \(n\) objects. A \(2\)-tuple is also called a pair, a \(3\)-tuple a triple, a \(4\)-tuple is a quadruple. The terminology was invented because \(12\)-tuple is easier to understand than duodecuple. (Wikipedia has an article on tuples.)

The comma operator is used to create tuples. Here is a quintuple (a 5-tuple):

In [1]:
1,2,3,4,5
Out[1]:
(1, 2, 3, 4, 5)

When you build a tuple, it is called packing the tuple. You can also unpack the tuple, storing the entries in variables. The following illustrates packing and then unpacking.

In [2]:
v = 1,2,3
x,y,z = v
print("v=", v, "; x=", x, "; y=", y, "; z=", z, sep="")
v=(1, 2, 3); x=1; y=2; z=3

Here is another example:

In [3]:
v = 1, 2+2, 3*3, "dog"
print("The vector v is",v)
x,y,z,name = v
print("x=", x, ", y=", y, ", z=", z, " and name=", name, sep="")
The vector v is (1, 4, 9, 'dog')
x=1, y=4, z=9 and name=dog

Remark (Print statement): Typically the print function separates adjacent arguments (e.g., "x=" and x above) by a space. This can be changed with the special sep argument. Above the separator was changed to an empty string (which means no separator). Some examples of using print in this way are available from the "Print Is A Function" section of the "What's new in Python 3" document.

Note you can also include parenthesis if it makes you happier or if you think it is more clear this way.

In [4]:
v = (1, 2+2, 3*3)
print("The vector v is",v)
(x,y,z) = v
print("x=", x, ", y=", y, " and z=", z, sep="")
The vector v is (1, 4, 9)
x=1, y=4 and z=9

Consider the following statement:

In [5]:
x,y = 1,2

In the expression above, first the expression on the right side of = is evaluated. This creates a pair \((1,2)\). Then the equals sign unpacks the pair, and stores the first value of the pair in x and the second value in the variable y. Here is evidence:

In [6]:
print("x is", x, "and y is", y)
x is 1 and y is 2

The following is a continuation of this example:

In [7]:
x,y = 1,2
print("Currently x=", x, " and y=", y, ".", sep="")
x,y = x+y, x*y
print("Now x=", x, " and y=", y, ".", sep="")
Currently x=1 and y=2.
Now x=3 and y=2.

Tuples are objects and can therefore be stored in a tuple. For example:

In [8]:
triangle = (0,0), (2,1), (3,5)
print(triangle)
((0, 0), (2, 1), (3, 5))

Here we have stored three \(2\)-tuples in a \(3\)-tuple called triangle. The \(2\)-tuples represent points in the plane which are the vertices of the triangle.

Example (Baricenter):

The baricenter of a triangle is the average of its coordinates. The following computes the baricenter of a triangle (given as a 3-tuple of vertices). This point is always inside the triangle.

In [9]:
def baricenter(triangle):
    p,q,r = triangle    # Store the vertices in p, q and r.
    x1,y1 = p           # Store the coordinates of p in x1 and y1.
    x2,y2 = q
    x3,y3 = r
    return (x1+x2+x3)/3, (y1+y2+y3)/3    # return the average
In [10]:
triangle = (0,0), (2,1), (3,5)
baricenter(triangle)
Out[10]:
(1.6666666666666667, 2.0)

Example (Fibonacci Numbers):

Directly accessing members of a tuple

You can access the objects in an \(n\)-tuple using square brackets. The objects are numbered \(0,1,\ldots, n-1\). (This convention differs from what is usually done in mathematics, where objects are numbered \(1\) to \(n\).) For example, consider the triangle again.

In [11]:
triangle = (0,0), (2,1), (3,5)

The first vertex can be accessed by:

In [12]:
triangle[0]
Out[12]:
(0, 0)

This can be done repeatedly, so the \(x\)-coordinate of the last vertex can be accessed with:

In [13]:
triangle[2][0]
Out[13]:
3

The number of elements in a tuple can be found using the len() function.

In [14]:
len(triangle)
Out[14]:
3
In [15]:
len(triangle[1])
Out[15]:
2

Tuples with length zero or one:

You can construct a \(1\)-tuple in one of two ways:

In [16]:
v = 1,
print(v, "is a", type(v).__name__, "of length", len(v))
w = (2,)
print(w, "is a", type(w).__name__, "of length", len(w))
(1,) is a tuple of length 1
(2,) is a tuple of length 1

There is also a \(0\)-tuple or emtpy tuple, which has no elements. You can build it with the function tuple():

In [17]:
v = tuple()
print(v, "is a", type(v).__name__, "of length", len(v))
() is a tuple of length 0

Remark: If x is any object in Python then type(x) returns its "type", and type(x).name gets the name of its type. See the documentation for the built in type function. (This is not very relevant for this course.)

Example (Average of numbers in a tuple):

The following computes the average of a students grades provided as a tuple.

In [18]:
def average(grades):
    n = len(grades)
    i=0
    total=0
    while i<n:
        total = total + grades[i]
        i = i+1
    return total/n
In [19]:
grades= 100, 90, 70, 80, 60, 100, 90
print("The students average is", average(grades))
The students average is 84.28571428571429

Iterating through a tuple:

In the above example, we used a while statement to iterate i through the indices of grades. We can use a for statement to iterate through the objects in a tuple. This is useful in cases when the value of the index is irrelevant.

If v is a tuple, then the statement "for x in v:" sets x equal to each object in the tuple v, and executes the subsequent block of code once with each such value.

In [20]:
v = 1, 2, 3, 4, 101, 3.14
for x in v:
    print(x)
1
2
3
4
101
3.14

Here is a modified version of the average() function which uses this:

In [21]:
def average(grades):
    total = 0
    for grade in grades:
        total =  total + grade
    return total/len(grades)

grades= 100, 90, 70, 80, 60, 100, 90
print("The student's average is", average(grades))
The student's average is 84.28571428571429

Concatenation of tuples:

You can concatenate (stick together) two tuples with the + operation.

In [22]:
v = 1,2,3
w = 3,4,5
x = v+w
print("The concatenation of v and w is", x)
The concatenation of v and w is (1, 2, 3, 3, 4, 5)

Ranges

A very useful type similar to a tuple is a range. If \(n\) is an integer, range(n) is essentially the same as the \(n\)-tuple (0, 1, 2, 3, ..., n-1). So, the following prints the numbers from 0 to 6.

In [23]:
for i in range(7):
    print(i)
0
1
2
3
4
5
6

If you call range with two arguments, you can specify a starting value and an ending value. So if \(a\) and \(b\) are integers with \(a<b\), range(a,b) can be thought of as the tuple (a, a+1, a+2, ..., b-1).

In [24]:
for i in range(100,105):
    print(i)
100
101
102
103
104

When range is called with three integer arguments as range(a,b,c), the third argument represents the step size. So this triple represents (a, a+c, a+2*b, ..., n) where \(n\) is a number satisfying \(b-c \leq n < b\). For example:

In [25]:
for i in range(5,55,5):
    print(i)
5
10
15
20
25
30
35
40
45
50

Sets

A set in Python is an unordered finite collection of objects. They can be created using curly bracket notation:

In [26]:
A = {1, 2, 4, 5, 9}

In order to define the empty set, you need to use set().

In [27]:
empty_set = set()
print(empty_set)
set()

Remark: The reason you need to do this is that the code {} returns an empty dictionary rather than an empty set. (We have not discussed dictionaries yet.)

Since a set is unordered, Python might order the elements when printed in a way different than you expect. For instance, if we print the set A above, we get:

In [28]:
print(A)
{9, 2, 1, 4, 5}

A set can not contain multiple copies of the same object. Observe:

In [29]:
B = {1, 2, 3, 2, 3, 2}
print(B)
{1, 2, 3}

You can iterate through elements of a set just like you did with a tuple.

In [30]:
import math
C = {1, math.pi, "Hello", False}
for c in C:
    print("One element of C is", c)
One element of C is False
One element of C is 1
One element of C is 3.141592653589793
One element of C is Hello

The "length" of a set is still well defined and returns the number of elements of a set. So, we have:

In [31]:
print("The set C has", len(C), "elements.")
The set C has 4 elements.

However sets are "unordered" so you can not access elements by index as with tuples as above. So if C is a set, the expression C[0] will result in an error. If you wanted to access the elements in this way, you could first convert the set to a tuple. This can be accomplished using tuple(C). See the below example:

In [32]:
Ctuple=tuple(C)
for i in range(len(C)):
    print("Element", i, "of C is", Ctuple[i], " and accessed by first converting to a tuple.")
Element 0 of C is False  and accessed by first converting to a tuple.
Element 1 of C is 1  and accessed by first converting to a tuple.
Element 2 of C is 3.141592653589793  and accessed by first converting to a tuple.
Element 3 of C is Hello  and accessed by first converting to a tuple.

You can also convert from a tuple to a set.

In [33]:
some_tuple = (1, 2, "Rhinoceros")
some_set =  set(some_tuple)
print(some_set)
{'Rhinoceros', 1, 2}

Adding an element to a set:

You can add an element to a set with the add method of a set:

In [34]:
A={1,2,3}
A.add("infinity")
print(A)
{1, 2, 3, 'infinity'}

Example (Union):

You could get a problem like this:
Write a function named union which takes as input two sets A and B and returns their union.
A possible solution using only what was introduced above is the following:

In [35]:
def union(A,B):
    C=set()         # Define C as the empty set
    for a in A:
        C.add(a)
    for b in B:
        C.add(b)
    return C

Lets test it.

In [36]:
A = {1,2,3}
B = {"A", "B", "C"}
union(A,B)
Out[36]:
{1, 2, 3, 'B', 'C', 'A'}
In [37]:
A = set()
B = set()
union(A,B)
Out[37]:
set()

Our union function seemed to work correctly in the examples above.

Testing for membership

The in keyword can be used to test for membership of both sets and tuples.

In [38]:
v = (1, 5, 9)
A = {1, 4, 13}
In [39]:
4 in v
Out[39]:
False
In [40]:
4 in A
Out[40]:
True

You can also use not in to test for the negation of membership.

In [41]:
4 not in v
Out[41]:
True
In [42]:
4 not in A
Out[42]:
False

Example (Subset):

You could get a problem like this:
Write a function called is_subset which takes two sets A and B and returns True if A is a subset of B and returns False if A is not a subset of B.
Here is a correct solution:

In [43]:
def is_subset(A,B):
    for a in A:
        if a not in B:
            return False
    return True
In [44]:
empty_set=set()
C={1,2,3}
is_subset(empty_set, C)
Out[44]:
True
In [45]:
is_subset(C, empty_set)
Out[45]:
False

List of operations for working with tuples:

In the following, we assume v and w are tuples. We also assume n is an integer.

tuple() Returns an empty tuple of length zero.
n,
(n,)
Both statements return an \(1\)-tuple whose only element is \(n\).
Here, \(n\) can be any object or number in Python.
len(v) Returns the length of v.
v[n] Returns the \((n+1)\)st item in the list. Here \(0 \leq n \leq len(v)\).
3 in v Tests if 3 appears somewhere in v, returning a boolean value.
3 not in v Tests if 3 does not appear somewhere in v, returning a boolean value.
v+w Returns the concatenation of v and w.
v.count(3) Returns the number of times 3 appears in v.
v.index(3) Returns the first index of 3 in v.
for x in v: Iterates through the objects appearing in v, running the indented block of code below once with x equal to each element of v.
tuple(z) Attempts to convert the object z to a tuple and returns the tuple. This works for sets, for example.

This list includes almost all operations available for working with tuples in Python. Some others are listed in the Common Sequence Operations section of the documentation for the Python standard library.

List of operations for working with sets:

In the following, we assume A and B are sets.

len(A) Returns the number of elements in A.
3 in A Tests if \(3 \in A\), returning a boolean value.
3 not in A Tests if \(3 \not \in A\), returning a boolean value.
for a in A: Iterates through the objects appearing in A, running the indented block of code below once with a equal to each element of A.
set() Returns the empty set.
set(z) Attempts to convert the object z to a set and returns the set. This works for tuples, for example.
A.add(3) Adds \(3\) to the set \(A\) changing \(A\) to \(A \cup \{3\}\).
A.remove(3) Removes \(3\) from \(A\) causing an error if \(3\) is not \(A\). If successful, this changes \(A\) to \(A \smallsetminus \{3\}\).
A.discard(3) Removes \(3\) from \(A\) if \(A\) contains \(3\) without causing an error if \(3 \not \in A\). This changes \(A\) to \(A \smallsetminus \{3\}\).
A.copy() Returns a copy of the set A.
Useful if you want to keep an original, but also make changes to the set such as adding elements.

In addition, there are several set-theoretic operations. These often have two notations.

A|B
A.union(B)
Returns the union \(A \cup B\).
A&B
A.intersection(B)
Returns the intersection \(A \cap B\).
A - B
A.difference(B)
Returns the set-theoretic difference \(A \smallsetminus B\).
A <= B
A.issubset(B)
Returns the boolean value of the statement \(A \subset B\), i.e., \(A\) is a subset of \(B\).
A >= B
A.issuperset(B)
Returns the boolean value of the statement \(A \supset B\), i.e., \(A\) contains \(B\).
A == B Tests for equality of sets returning a boolean value.

This does not list all available operations. More can be found in the Set Types section of the Python standard library reference.

Remark. Even though these set-theoretic operations are available, you should be able to implement your own using more basic operations from the first table as in the examples above.

More examples

Example (GCD):

The greatest common divisor of two non-negative integers \(a\) and \(b\) which are not both zero is the largest integer which evenly divides both \(a\) and \(b\). The following is The Euclidean Algorithm to find the gcd of \(a\) and \(b\).

In [46]:
def gcd(a,b):
    if a>b:   # Ensure that a<=b:
        (a,b) = (b,a)  # Swap the values of a and b if a>b.
    while a!=0:
        (a,b) = (b%a,a)
    return b

Here is an explanation for why it works. Observe that gcd is symmetric: \(gcd(a,b)=gcd(b,a)\). This means we can always assume that a<=b. Then it should be observed that an integer divides \(a\) and \(b\) evenly if and only if it divides \(a\) and \(b\%a\) evenly. So \(gcd(a,b)=gcd(b\%a,a)\). Since \(0 \leq b\%a < a\), the numbers we see are decreasing and non-negative. So eventually the smallest number reaches zero. Finally we observe that \(gcd(0,b)=b\). Since the \(gcd\) of all pairs we have looked at is the same, the current value of \(b\) must be the \(gcd\).

Here is a test:

In [47]:
for n in range(1,25):
    print("The GCD of 12 and", n, "is", gcd(12,n))
The GCD of 12 and 1 is 1
The GCD of 12 and 2 is 2
The GCD of 12 and 3 is 3
The GCD of 12 and 4 is 4
The GCD of 12 and 5 is 1
The GCD of 12 and 6 is 6
The GCD of 12 and 7 is 1
The GCD of 12 and 8 is 4
The GCD of 12 and 9 is 3
The GCD of 12 and 10 is 2
The GCD of 12 and 11 is 1
The GCD of 12 and 12 is 12
The GCD of 12 and 13 is 1
The GCD of 12 and 14 is 2
The GCD of 12 and 15 is 3
The GCD of 12 and 16 is 4
The GCD of 12 and 17 is 1
The GCD of 12 and 18 is 6
The GCD of 12 and 19 is 1
The GCD of 12 and 20 is 4
The GCD of 12 and 21 is 3
The GCD of 12 and 22 is 2
The GCD of 12 and 23 is 1
The GCD of 12 and 24 is 12

Here is a GCD table:

In [48]:
print("GCD ", end="")
for j in range(1,10):
    print(j,end=" ")
print()
for j in range(21):
    print("-", end="")
print()
for i in range(1,10):
    print(i, "|" ,end=" ")
    for j in range(1,10):
        print(gcd(i,j), end=" ")
    print()
GCD 1 2 3 4 5 6 7 8 9 
---------------------
1 | 1 1 1 1 1 1 1 1 1 
2 | 1 2 1 2 1 2 1 2 1 
3 | 1 1 3 1 1 3 1 1 3 
4 | 1 2 1 4 1 2 1 4 1 
5 | 1 1 1 1 5 1 1 1 1 
6 | 1 2 3 2 1 6 1 2 3 
7 | 1 1 1 1 1 1 7 1 1 
8 | 1 2 1 4 1 2 1 8 1 
9 | 1 1 3 1 1 3 1 1 9 

Example (Sum of squares)

The following is a simple function which checks if a integer \(n\) can be written as a sum of two squares of integers \(a\) and \(b\), \(n=a^2+b^2\). It will return such a pair \((a,b)\) if \(n\) can be written as a sum of squares and will return None if it can not.

In [49]:
def sum_of_squares(n):
    a=0
    while a**2<=n:
        b=0
        while a**2+b**2<=n:
            if a**2+b**2==n:
                return (a,b)
            b=b+1
        a=a+1
    return None

Here is why it works. The pair of while loops visit all pairs of non-negative integers \((a,b)\) which satisfy \(a^2+b^2<=n\). If one of the pairs achieves equality, we return that pair. Otherwise we return None.

This is probably not the fastest algorithm. For instance once you know \(a\), it must be that \(b=\sqrt{n-a^2}\). We could calculate this explicitly and check if it is an integer. This might yield a faster algorithm.

Here is a function which just prints a string according to the output of our function sum_of_squares(n).

In [50]:
def print_sum_of_squares(n):
    output = sum_of_squares(n)
    if output is None:
        print(n,"is not a sum of squares.")
    else:
        # Now we know the output is a pair of integers.
        (a,b) = output
        print(n," = ",a,"^2 + ",b,"^2.", sep="")
In [51]:
for n in range(20):
    print_sum_of_squares(n)
0 = 0^2 + 0^2.
1 = 0^2 + 1^2.
2 = 1^2 + 1^2.
3 is not a sum of squares.
4 = 0^2 + 2^2.
5 = 1^2 + 2^2.
6 is not a sum of squares.
7 is not a sum of squares.
8 = 2^2 + 2^2.
9 = 0^2 + 3^2.
10 = 1^2 + 3^2.
11 is not a sum of squares.
12 is not a sum of squares.
13 = 2^2 + 3^2.
14 is not a sum of squares.
15 is not a sum of squares.
16 = 0^2 + 4^2.
17 = 1^2 + 4^2.
18 = 3^2 + 3^2.
19 is not a sum of squares.

Remark: Playing with the sum_of_squares function could potentially lead you to experimental evidence of interesting theorems in mathematics such as Fermat's theorem which characterizes the primes that are the sum of two squares.

Example (Cartestian Product):

The Cartestian product of two sets \(A\) and \(B\) is the collection of pairs \((a,b)\) where \(a \in A\) and \(b \in B\). We will write a function which takes as input two sets, and returns their Cartesian product.

In [52]:
def cartesian_product(A,B):
    C = set()                # C is the empty set
    for a in A:
        for b in B:
            C.add( (a,b) )
    return C

Here is a test:

In [53]:
A = {1,2,3}
B = {"A", "B", "C"}
C = cartesian_product(A,B)
print(C)
{(2, 'C'), (2, 'A'), (3, 'B'), (2, 'B'), (1, 'A'), (3, 'A'), (3, 'C'), (1, 'C'), (1, 'B')}

In [54]:
(3, "A") in C
Out[54]:
True

Exercises:

Please try to do these for practice. Some of these problems may be assigned for homework.

  1. A divisor of an integer \(n\), is an integer \(d\) so that \(d\) divides \(n\), i.e., so that \(\frac{n}{d} \in {\mathbb Z}\). Write a function whose name is divisors which takes as input an integer \(n\) and returns the set of positive divisors of \(n\).
  2. Using the previous problem, write an function named gcd2 which takes as input two positive integers \(a\) and \(b\) and returns their greatest common divisor. Instead of using Euclid's algorithm, use the previous part to compute the two sets of divisors of the numbers. Then intersect these sets and find the maximal element. Note that in Python, you can write max(S) to find the maximal element of the set \(S\). (Remark: This function is much more inefficient than Euclid's algorithm!)
  3. Write a function named intersection which takes as input two sets \(A\) and \(B\) and returns the intersection of \(A\) and \(B\). Do not use the intersection methods defined by Python. You should be able to do this with the set() function for constructing the empty set, one for loop for looping through elements of a set, the in statement for testing membership, and the add method for adding elments to a set.
  4. Write your own function named max2 which takes as input a tuple \(t\) of numbers and returns the maximal element of \(t\). Do not use the max function mentioned above, instead loop through the elements of \(t\) to find the maximal element.
  5. Suppose \(A\) and \(B\) are two sets of numbers. Their sumset is the set \[\{a+b~:~a \in A \text{ and } b \in B\}.\] Write a function called sumset which takes as input two sets of numbers \(A\) and \(B\) and returns their sumset.
  6. Write a function set_of_squares(n) which takes as input a natural number \(n\) and returns the set \[A_n=\{k^2:~k \in {\mathbb Z} \text{ and } 0 \leq k \leq n\}.\]
  7. For sets of numbers \(A\) and \(B\), let \(A \oplus B\) denote their sumset as defined two problems above. For \(n \in {\mathbb N}\), let \(A_n\) be as in the previous problem. Use the functions defined in the two prior problems to compute \[(A_n \oplus A_n) \oplus (A_n \oplus A_n)\] for small values of \(n\). Let \(A_\infty=\{k^2: k \in {\mathbb Z}\}\). Use the results of this calculation to formulate a conjecture about the nature of the set \[(A_\infty \oplus A_\infty) \oplus (A_\infty \oplus A_\infty).\] (Remark. Sets in Python are sometimes printed out of order. If you have a set X and want to see it in order, you can first convert it to a list with L=list(X). Then you can sort it with L.sort(). Then printing L printes the members of X in order. Lists will be covered soon.)
  8. Lagrange's four-square theorem states that any non-negative integer is the sum of the squares of four integers. Write a function lagrange_four_square(n) which takes as input a non-negative integer \(n\) and returns a quadruple \((a,b,c,d)\) of integers so that \(n=a^2+b^2+c^2+d^2\).
  9. Suppose \(A\), \(B\) and \(C\) are subsets of \({\mathbb Z}\). Consider the quantified statement \[\star: \forall a \in A ~ \exists b \in B \text{ such that } a-b \in C.\] Write a function called verify_star which takes as input three sets of integers \(A\), \(B\) and \(C\) and returns the truth-value of \(\star\) (i.e., returns True or False depending on the truth value of \(\star\) in this case).
  10. Write a function planar_distance which takes as input two points in the plane and returns the distance between them. Here a point in the plane should be interpreted as a \(2\)-tuple whose entries are both real numbers.
  11. Let \(\epsilon>0\). Say that a triangle is \(\epsilon\)-nearly equilateral if for any two side lengths of the triangle \(s_1\) and \(s_2\), the ratio \(\frac{s_1}{s_2}\) is less than \(1+\epsilon\). Write a function is_nearly_equilateral(P,Q,R,epsilon) which takes as input three points in the plane \(P\), \(Q\) and \(R\) as well as a positive parameter epsilon and returns the truth-value of the statement "The triangle \(PQR\) is epsilon-nearly equilateral. (Remark: Why is unreasonable to use a function called is_equilateral(P,Q,R) which returns the truth-value of "The triangle \(PQR\) is equilateral?")
  12. Write a function is_square which takes as input four points in the plane with integer coordinates and returns the truth-value of the statement "The four points are the vertices of a square."

References