Oregon Curriculum Network
Discovering Math with Python

Chapter 3: A FIRST CLASS

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]:
function

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.

Mathematical Types

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]:
array([[ 1.,  0.,  0.,  0.,  0.],
       [ 0.,  1.,  0.,  0.,  0.],
       [ 0.,  0.,  1.,  0.,  0.],
       [ 0.,  0.,  0.,  1.,  0.],
       [ 0.,  0.,  0.,  0.,  1.]])

In [3]:
m = np.matrix('[1, 2; 3, 4]')
m


Out[3]:
matrix([[1, 2],
        [3, 4]])

In [4]:
m_inv = m.getI()
m_inv


Out[4]:
matrix([[-2. ,  1. ],
        [ 1.5, -0.5]])

In [5]:
m * m_inv  # within floating point error, the identity matrix


Out[5]:
matrix([[  1.00000000e+00,   1.11022302e-16],
        [  0.00000000e+00,   1.00000000e+00]])

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]:
10888869450418352160768000000

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]:
P class: (('a', 'a'), ('b', 'b'), ('c', 'c'))...

In [9]:
p = p.shuffle()
p


Out[9]:
P class: (('a', 'b'), ('b', 'c'), ('c', 'f'))...

In [10]:
p.encrypt('able was i ere i say elba')


Out[10]:
'bcuxp blpnpxrxpnplbypxucb'

In [11]:
p.decrypt(_)  # reuse the most recent result


Out[11]:
'able was i ere i say elba'

In [12]:
q = ~p  # get the inverse
I = q * p

In [13]:
I # is it true?  Is I the identity permutation?


Out[13]:
P class: (('b', 'b'), ('c', 'c'), ('f', 'f'))...

In [14]:
I.encrypt("this will do nothing hooray for identity permutation")


Out[14]:
'this will do nothing hooray for identity permutation'

Properties of a Group

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:

  • Closure (two elements multiplied always give another element in the set)
  • Associativity (p q) r == p (q r)
  • Inverses (such that p * ~p is the neutral element)
  • Neutral Element (Identity)

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]:
'q'

In [16]:
terminus = q[interim] # something goes to final stop
terminus


Out[16]:
'i'

In [17]:
pq = p * q
terminus == pq['a']    # should be true


Out[17]:
True

In [18]:
p * q == q * p


Out[18]:
False

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]:
(('a',
  'i',
  'j',
  's',
  'f',
  'c',
  'n',
  'u',
  'd',
  'v',
  'o',
  'h',
  'y',
  'b',
  'w',
  'm',
  'r',
  'p',
  'l',
  'q',
  'e',
  't',
  'z'),
 ('g',),
 ('k',),
 ('x', ' '))

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]:
P class: (('a', 'g'), ('b', 'k'), ('c', 'z'))...

In [22]:
c = p.encrypt("this is a test this is only a test")
c


Out[22]:
'ftq pq pgpfl fpftq pq panhjpgpfl f'

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]:
'this is a test this is only a test'

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:

  • that Python comes with data structures, and has even more in 3rd party world
  • we have function syntax to build chunks of functionality
  • functions become internalized, indented under the class keyword, to define new types
  • we can use class syntax to define what operators will do, and even syntax like square brackets, as when we go p['a'] to see what 'a' maps to.

On to Chapter 4: Clock Arithmetic
Back to Chapter 2: Functions At Work
Introduction