Oregon Curriculum Network
Discovering Math with Python
We're still unpacking the Executive Summary of what Python is. Python is an interpreted, object-oriented, high-level programming language with dynamic semantics.
What does "object-oriented" mean? Have we looked at that yet?
Yes and no.
We've been making use of the built-in types that Python provides, including the function type, and several data structures, each with its own bag of tricks. However, we've yet to define our own types. That's what this chapter is about, how to do that.
The function we didn't finish at the end of Chapter 2, is supposed to take a cyclic representation of a permutation, and return a dict. By this chapter's end, we'll have an implementation, but as a method of a class rather than as a free-standing function.
Here's what we ended with:
In [1]:
def inv_cyclic(cycles : tuple) -> dict:
"""stub function: doesn't do anything yet"""
output = {} # empty dict
pass # more code goes here
return output
type(inv_cyclic)
Out[1]:
Lists know how to append. Sets know how to participate in union and intersection operations. A numpy matrix will invert itself, in the linear algebra sense, if we use the right type of matrix (not just an ordinary numpy array). A dict may be updated with another dict.
The idea of a type of object, is that to each type there corresponds a set of methods, characteristic of that type.
This style of thinking was not meant to seem "out of the blue" but is rather meant to imitate what we might consider everyday human language grammar. We know that Dog type animals have characteristic behaviors and attributes, such as a propensity to bark, wag a tail, eat.
Mathematics provides a rich set of types which, like animals, come with their own characteristic behaviors. Some add and multiply, others only multiply, or only add. Some may be inverted, though what that means exactly will vary with the type.
In Python, we get various operators and other syntax that we see many types of objects use.
For example not only integers can add.
Strings can too, but for them, using the plus symbol results in concatenation. "ABC" + "DEF" gives the string "ABCDEF".
What's true, though, is both numbers and strings have a use for "add" as designated by the + (plus sign).
When it comes to mathematical concepts such as "multiply" and "inverse" these often go together, as we explore in this chapter.
An object times its inverse, if defined, typically yields what we call the multiplicative identity element, such that p * I = I * p = p i.e. multiplying anything by I leaves that anything unchanged.
That's what we mean by "identity element" (or "neutral element" in some texts).
We have an identity element associated with addition as well, named zero. p + I = I + p = p when I is zero, and p plus the additive inverse of p (e.g. 3 + (-3)) is likewise I (0).
A matrix times its own inverse gives the identity matrix, which if you know linear algebra looks like this:
In [2]:
import numpy as np
I = np.identity(5)
I
Out[2]:
In [3]:
m = np.matrix('[1, 2; 3, 4]')
m
Out[3]:
In [4]:
m_inv = m.getI()
m_inv
Out[4]:
In [5]:
m * m_inv # within floating point error, the identity matrix
Out[5]:
Even without knowing what a matrix is, or how to multiply them, the idea the a pair of objects might be inverses of one another, such that their product is 1 (one), is familiar, from ordinary number types. 2 and 1/2 are inverses in this sense, because 2 * (1/2) equals 1.
In this chapter, we'll create a template for a type of object called a Permutation, or P for short. P-objects will have inverses and p * ~p (p times inverse p) will give the Identity permutation.
What would be the identity permutation? A permutation that maps every element to itself, such as 'a' to 'a', 'b' to 'b' and so on. Encrypting a message with the identity cipher would not change the message one bit.
We're going to want our permutations to multiply apparently, and take the unary operator ~ for "invert", such that p * ~p turns out to be legal Python. Just as we might multiply matrices together, as above, we'd like to multiply permutations. How might this be arranged?
Below is a lot more code in a single cell than we've yet seen. We're defining the blueprint for a P-type object, a Permutation. The objects made from this template are the "selves" i.e. each has a unique "self" that it brings to the table, when a method is run.
p.shuffle( ) actually triggers P.shuffle(p) behind the scenes, meaning p gets to be its own first argument to P.shuffle, which is why we write self as the first parameter. The interpreter itself supplies that argument, knowing p has one, or is one (a self).
Instances all share the same methods, but as selves each has room for it's own data, distinct from that of the other selves. We plan to make this clear.
Think of how many permuations one might build from the 27 elements we've been using. The letter 'a' could map to 27 other elements, including itself. Every possible ordering of a-z plus space is fair game. That's 27 factorial, a huge number.
In [6]:
import math
math.factorial(27)
Out[6]:
Even so, that's a finite number, once the number of elements (27) is fixed. Think of each of those possible permuations as a "self" (an instance) all of which have methods in common, as implemented in the source code below:
In [7]:
from random import shuffle
from string import ascii_lowercase # all lowercase letters
class P:
"""
A Permutation
self._code: a dict, is a mapping of iterable elements
to themselves in any order.
"""
def __init__(self, iterable = ascii_lowercase + ' '): # default domain
"""
start out with Identity
"""
try: # just making sure the caller passed in some iterable object
seq1 = iter(iterable)
seq2 = iter(iterable)
except:
raise TypeError # don't pass in a single integer for example
self._code = dict(zip(seq1, seq2)) # identity, elements self-paired.
def shuffle(self):
"""
return a random permutation of this permutation
__init__ narrowed it down to the raw material, e.g. what
letters or numbers make up the core _code
"""
# use shuffle
# something like
the_keys = list(self._code.keys()) # grab keys
shuffle(the_keys) # shuffles 'em
newP = P()
# inject dict directly...
newP._code = dict(zip(self._code.keys(), the_keys))
return newP
def encrypt(self, plain):
"""
turn plaintext into cyphertext using self._code
Pass through any symbol the _code may not mention
"""
output = "" # empty string
for c in plain:
output = output + self._code.get(c, c)
return output
def decrypt(self, cypher):
"""
Turn cyphertext into plaintext using ~self
Unmentioned elements stay as is.
"""
reverse_P = ~self # invert me!
output = ""
for c in cypher:
output = output + reverse_P._code.get(c, c)
return output
def __getitem__(self, key):
"""
square bracket notation, used against a P-object,
effectively passes through to _code dict.
Don't raise a KeyError if there's no value,
return None instead
"""
return self._code.get(key, None)
def __repr__(self):
"""
Note showing the whole of _code for brevity
"""
return "P class: " + str(tuple(self._code.items())[:3]) + "..."
def cyclic(self):
"""
cyclic notation, a compact view of a group, see
Chapter 2.
"""
output = []
the_dict = self._code.copy()
while the_dict:
start = tuple(the_dict.keys())[0]
the_cycle = [start]
the_next = the_dict.pop(start)
while the_next != start:
the_cycle.append(the_next)
the_next = the_dict.pop(the_next)
output.append(tuple(the_cycle))
return tuple(output)
def __mul__(self, other):
"""
look up my keys to get values that serve
as keys to get other's "target" values
"""
new_code = {}
for c in self._code: # going through my keys
target = other._code[ self._code[c] ]
new_code[c] = target
new_P = P(' ') # start a new permutation
new_P._code = new_code # inject new_code
return new_P
def __invert__(self):
"""
create new P with reversed dict
"""
newP = P(' ')
newP._code = dict(zip(self._code.values(), self._code.keys()))
return newP
def __eq__(self, other):
"""
are these permutation the same?
Yes if self._cod==e other._code
"""
return self._code == other._code
Just going by the names of the methods, which look like functions, indented under the keyword class, we see ideas developed in chapter 2, around encrypting and decrypting. The main difference is the bare dictionary form of our permutation will be named _code and used internally. We're then adding capabilities that bare dictionaries do not have, such as the ability to multiply, or invert thanks to a single operator.
In [8]:
p = P()
p
Out[8]:
In [9]:
p = p.shuffle()
p
Out[9]:
In [10]:
p.encrypt('able was i ere i say elba')
Out[10]:
In [11]:
p.decrypt(_) # reuse the most recent result
Out[11]:
In [12]:
q = ~p # get the inverse
I = q * p
In [13]:
I # is it true? Is I the identity permutation?
Out[13]:
In [14]:
I.encrypt("this will do nothing hooray for identity permutation")
Out[14]:
So you see the matrix type (numpy.matrix) and the permuation type (P) have some similarities. In Group Theory, a branch of mathematics, we talk about the properties of a group, a set of objects and an operation, usually called multiplication.
These properties are:
Some groups are also Abelian, meaning their operation is also Commutative, not just Associative.
These concepts might seem foreign to learning a computer language such as Python, but Closure should remind you of types, and how two objects of the same type may or may not result in a new object of that type.
For example two integers always add to give an integer, but the multiplicative inverse of an integer is not an integer except in the case of 1 itself. 2 * (1/2) equals 1. 1/2 is the inverse of 2. The set of integers is not a group with respect to multiplication, as one property of a Group is every object has its inverse.
So what does it mean to "multiply" two permutations anyway? If the first one maps 'a' to 'q' and the second maps 'q' to 'k', then their product permutation takes us right from 'a' to 'k'. You could think of multiplying as a kind of "chaining" or "pipelining" in this case.
In [15]:
p = P().shuffle() # quick way to start out randomized
q = P().shuffle() # another one
interim = p['a'] # a goes to something
interim
Out[15]:
In [16]:
terminus = q[interim] # something goes to final stop
terminus
Out[16]:
In [17]:
pq = p * q
terminus == pq['a'] # should be true
Out[17]:
In [18]:
p * q == q * p
Out[18]:
Multiplication is not Commutative in this case.
Lets take a look at pq as a tuple of cyclic subgroups. We call them subgroups because each tuple describes a permutation with the Group properties above.
In [19]:
cyc = pq.cyclic()
cyc
Out[19]:
Lets start though, by completing our function from the last chapter. We'll morph it into the method from_cyclic and have it it build us a new P-object. Lets do that by refactoring, having the P object inherit from another class:
In [20]:
class P_base:
"""
A Permutation
self._code: a dict, is a mapping of iterable elements
to themselves in any order.
"""
def __init__(self, iterable = ascii_lowercase + ' '): # default domain
"""
start out with Identity
"""
try:
seq1 = iter(iterable)
seq2 = iter(iterable)
except:
raise TypeError
self._code = dict(zip(seq1, seq2))
def __getitem__(self, key):
return self._code.get(key, None)
def __repr__(self):
return "P class: " + str(tuple(self._code.items())[:3]) + "..."
def __mul__(self, other):
"""
look up my keys to get values that serve
as keys to get others "target" values
"""
new_code = {}
for c in self._code: # going through my keys
target = other._code[ self._code[c] ]
new_code[c] = target
new_P = P()
new_P._code = new_code
return new_P
def __eq__(self, other):
"""
are these permutation the same?
Yes if self._cod==e other._code
"""
return self._code == other._code
class P(P_base): # first use of inheritance
def __invert__(self):
"""
create new P with reversed dict
"""
newP = P()
newP._code = dict(zip(self._code.values(), self._code.keys()))
return newP
def shuffle(self):
"""
return a random permutation of this permutation
"""
# use shuffle
# something like
the_keys = list(self._code.keys()) # grab keys
shuffle(the_keys) # shuffles 'em
newP = P()
# inject dict directly...
newP._code = dict(zip(self._code.keys(), the_keys))
return newP
def encrypt(self, plain):
"""
turn plaintext into cyphertext using self._code
"""
output = "" # empty string
for c in plain:
output = output + self._code.get(c, c)
return output
def decrypt(self, cypher):
"""
Turn cyphertext into plaintext using ~self
"""
reverse_P = ~self # invert me!
output = ""
for c in cypher:
output = output + reverse_P._code.get(c, c)
return output
def cyclic(self):
"""
cyclic notation, a compact view of a group
"""
output = []
the_dict = self._code.copy()
while the_dict:
start = tuple(the_dict.keys())[0]
the_cycle = [start]
the_next = the_dict.pop(start)
while the_next != start:
the_cycle.append(the_next)
the_next = the_dict.pop(the_next)
output.append(tuple(the_cycle))
return tuple(output)
def from_cyclic(self, incoming):
"""
create a P-type object from incoming cyclic view
Think of zipping ('a', 'c', 'q', 'k') with
('c', 'q', 'k', 'a') -- the pairs ('a', 'c'),
('c', 'q'), ('q', 'k') and ('k', 'a') are what
dict() will then consume. We go through each
subgroup, updating the final dict with the results
of each loop. When done, dump the dict into _code.
"""
output = {}
for subgroup in incoming:
output.update(dict(zip(subgroup, subgroup[1:] + tuple(subgroup[0]))))
newP = P()
newP._code = output
return newP
class P will do everything class P_base does, and then some. This may not be the best illustration of how inheritance works, and what it means, but it will do for now. We might imagine an alternative class, inheriting from P_base, that implements a different assortment of methods. We'll get to an example soon.
In [21]:
p = P().shuffle()
p
Out[21]:
In [22]:
c = p.encrypt("this is a test this is only a test")
c
Out[22]:
In [23]:
cyclic_view = p.cyclic() # get the tuple of tuples
In [24]:
test_p = P().from_cyclic(cyclic_view) # test our new method
In [25]:
test_p.decrypt(c) # does the new permutation decrypt with the old one encrypted?
Out[25]:
The Standard Library includes a unittest module that would allow us to formalize the above testing.
In Test Driven Development (TDD) we might write the tests first, giving expected outcomes, even before we flesh out the stub function or method we hope to build. We'll get to that in another chapter.
In the meantime, look at what you've learned:
On to Chapter 4: Clock Arithmetic
Back to Chapter 2: Functions At Work
Introduction