In the viewpoint of object-oriented programming (OOP), objects contain data in the form of attributes and code in the form of methods. Python is a class-based language, where the class of an object determines its type; an object is a programming construct that can refer to itself, has certain data associated with itself, and can act in certain ways.
Permutations provide an exceptional introduction to the topic of OOP since every permutation is an interesting object in its own right (as a group element) but also performs an action (as a function)! For implementation purposes, we will only consider permutations with a finite domain.
A strong benefit to the OOP mode of thinking is that it eliminates much type checking: functions which act on an object in a specific class can be written under the assumption that the object is, in fact, a valid class member. For instance, if we want to determine the disjoint cycle notation for a permutation written in one-line notation, our cycle code doesn’t need to check to see whether the one-line notation validly defines a permutation, since that is handled when new permutation objects are named.
Subsection2.2.1Classes
Technology2.2.2.The class command.
Classes in Python are defined via a block structure, similarly to functions.
class MyClass:
statement_1
statement_2
...
statement_n
Listing2.2.3.Python class definition
Most of the statement_i lines at the first level of indentation to a class definition should be the definitions of methods. Assignments at the first level of indentation define class attributes, the values of which are held in common by all members of the class. Object attributes are defined within methods.
A method is a function defined within the first level of indentation of a class, and the first argument to a method is special: it is the name used within the method to refer to the object itself. In Python, the convention is to use self as the name for the first argument, and every method should require it.
Mathematicians love the class/object organization, whether or not they know it: think about a proof which begins with the words, “let \(p/q\) be a rational number.” Once the statement is pronounced, there are so many truths implied about \(p\text{,}\)\(q\text{,}\) and \(p/q\text{,}\) all of which come just from knowing that \(p/q\in\Rats\text{.}\) All of that works because we recognize that the object named \(p/q\) is a particular instance of the class of things called rational numbers.
Activity2.1.Permutation project files.
In this project, we’ll be working in tandem in two files, the first containing our Class definition and the second being our main execution file. We want to separate the two so that we can use our permutation class file later in other projects via the import command without generating a bunch of output relating to this current project.
(a)
Using IDLE, create a blank Python module file called AlgoPerm.py in the same easy-to-find folder on your computer as you used for KidRSA project files. The header information should have a file title of Math 3380 Permutations Class.
(b)
Create another blank file in the same location, called aam_proj2.py, and give it the correct header information.
(c)
On the first non-comment line of aam_proj2.py, insert the command from AlgoPerm import *. This will allow you to use all of the classes and functions defined in the AlgoPerm.py module in this file.
(d)
Start the class definition at the bottom of the file using
class AlgoPerm:
"""A class of permutations useable for AAM."""
Subsection2.2.2Creating new objects
Given an empty class definition we cannot do anything. In order for a class to be useful it must be possible to create objects in the class. This is variously called instantiation or initialization.
Definition2.2.4.Instantiation.
An instance is a particular member of a class. Class instantiation is the declaration that a named object belongs to a certain class. For example, declaring “Fido is a dog” is an instantiation of the class of “dog” to the object named “Fido”. Mathematically, this is allows an existential quantification: there exists a dog, named Fido.
A slightly less complicated way of thinking of this is to recognize that until a value is assigned to a variable name, the variable name does not mean anything to Python. Instantiation is the way of giving a type to a particular name. For a simple type like int, we do this just by assigning the value to a name: bob = 5. However we could first instantiate that bob is to be an integer, by declaring bob = int(), but in this case the int class comes equipped with a default value.
>>> bob = int(); print(bob)
0
Listing2.2.5.Predefined types do not require instantiation, but permit it.
Technology2.2.6.Python object instantiation.
Important methods for Python classes often have a strange naming convention, having the form __methodname__. The first of these we will use is the initialization method, called __init__. It is very important that the __init__ method must have at least the self argument, along with arguments for any other information which must be known when creating a new object.
class MyClass:
"""This is the class docstring which is printed by `help(MyClass)`"""
def __init__(self, *args, **kwargs):
statement_1
statement_2
statement_3
...
Listing2.2.7.The __init__ method for a class definition
After executing this class block containing a valid __init__ method, all that is necessary to create a new MyClass object is to assign the class to a name.
Using the class name MyClass as a function invokes the __init__ method in such a way that the name new_obj is associated with an object of MyClass and then automatically used as the self argument of the __init__ method.
Technology2.2.8.Function argument lists.
In Listing 2.2.7 we see two special arguments used in a function definition, *args and **kwargs. The names of the local variables defined by these arguments are respectively args and kwargs. The first, args, consists of a tuple of all positionally-determined arguments passed to the function. The second, kwargs, consists of a dictionary whose keys are the keywords of arguments passed to the function, and the associated values are the values of those arguments.
>>> def my_func(*args, **kwargs):
... print(type(args), len(args))
... print(type(kwargs), list(kwargs.items()))
... >>> my_func(13, 17, 19,
... keya="a first keyword argument"
... keyb="A SECOND!!" )
<class 'tuple'> 3
<class 'dict'> [('keya', 'a first keyword argument'), ('keyb', 'A SECOND!!')]
When defining a method for a class there are vanishingly few cases where the method does not need to be able to refer to the object on which it is called. This referent object is most often called self and is always the first argument of the function definition.
Remember: even if you forget to name the first argument to a method self, it always takes the value of the object on which the method is called, regardless of whether or not other arguments are provided or needed by the method definition.
We have specified that the domain and the mapping are the two pieces of information necessary to specify a permutation, and that makes perfect sense. However, if one-line or two-line notation is the format in which a permutation is specified, then the domain need not be listed separately.
Activity2.2.Start the __init__ method.
Explain why the following might be a good start to the __init__ method and write a docstring that explains how the arguments are used.
class AlgoPerm:
"""A class of permutations for use in Math 3380 Algorithms."""
def __init__(self, mapping, domain=None):
"""docstring"""
# Check to see whether mapping provides a valid permutation.
'Valid'
# Check to see whether a domain was given, and if so, check
# that it agrees with the domain of the mapping.
'Domain works'
# Convert the given mapping into a 'canonical' storage format
# and assign it to an attribute.
'Assign mapping'
# Assign any other interesting attributes
'Assign attributes'
One other method should be built into a minimal working class definition. The __repr__(self) method is a method which must always return a str and generally should return a string which provides valid input to the __init__ method. This will be discussed after considering what valid input means in the first place!
Subsection2.2.3Input validation
Input validation is required whenever there is a possibility that any user of code (including the original programmer) might make a mistake on using the code that renders the code incorrect. It takes some extra work to make sure that you have covered all the possible input cases and either correctly handled them or provided meaningful error messages. That said, there is a serious benefit to having performed a strong input validation on the __init__ method of a class: now everything in the class is guaranteed to have the right form. You never need to wonder whether or not self is going to have the correct attributes and work correctly.
In order to begin a class of permutations, we first need a clear understanding of what we should consider to be valid input to a permutation. Once we can describe what data is necessary and sufficient to determine the permutation uniquely, we can construct an algorithm to determine whether input satisfies the criteria, and then implement the algorithm. For now, we will restrict our permutations to permutations of \(\set{1,2,3,\dotsc,n}\text{;}\) the group of these permutations is \(\sym{n}\text{.}\)
As a first consideration, we already know that a good way to map arbitrary data in Python to other arbitrary data is via a dictionary, and in fact this is a great way to think of two-line notation for a permutation. The only validation which needs to take place is to make sure that the sets of keys and of values of a dictionary given as the mapping argument to AlgoPerm.__init__(...) are equal.
Technology2.2.11.dict.keys(), dict.values(), and dict.items() methods.
The methods dict.keys() and dict.values() produce list-like objects containing the keys and values respectively of a dict. dict.items() produces a list-like object containing tuples (k,v) where k is a key and v its associated value. All three outputs are iterable.
Listing2.2.12.Keys and values of dict show unexpected behavior
As demonstrated above, it is unclear by casual inspection whether the keys or values of a dictionary are in fact equal by using just the dict.keys() and dict.values() methods! Be careful.
If a list is to be used as the one-line notation for a permutation in \(\sym{n}\text{,}\) then the list must then be a rearrangement of the numbers \(\set{1,2,\dotsc,n}\text{.}\)
Fact2.2.13.
A list named in_list represents the one-line notation of a permutation if and only if the maximum element of in_list is M and when sorted the values of in_list correspond to the values of range(1, M+1).
This allows us to introduce some new tools.
Technology2.2.14.Python min and max built-in functions.
The min function can be used in two ways: if given a single iterable argument arg1, then min(arg1) returns the minimum element of arg1. Given two or more arguments, min(arg1, arg2, ...) returns the minimum argument. As should be expected, max behaves in the corresponding manner but returns the maximum value.
It is not always clear what ordering is used among comparable items.
>>> min("This is a string")
' '
>>> max("Bob", "bob", "Larry")
'bob'
Listing2.2.15.An example using the min and max commands in Python
Technology2.2.16.Python sorted built-in function.
Given an iterable argument arg1, the built-in function sorted(arg1) returns an increasing sorted list of the contents of arg1.
>>> sorted("This is a string".split())
['This', 'a', 'is', 'string']
Listing2.2.17.An example of the sorted built-in Python function
That example also contains a sneaky example of the str.split() method. The ordering used on strings is lexicographic (dictionary) ordering with the caveat that the order of characters is per their ordinal, via the ord function.
Now we write an algorithm which applies Fact 2.2.13.
Algorithm2.2.18.Verifying that a sequence is one-line notation.
Suppose that for some fixed \(n\in\Zp\) a sequence \(a = (a_i:i\in [n])\) is given, and let \(s\) be a function which sorts sequences in ascending order.
Let \(M = \max(a_i:i\in[n])\text{.}\)
If \(s(a) = s([M])\text{,}\) then \(a\) is the one-line notation of a permutation of \([M]\text{.}\)
For maximum flexibility we will define the canonical data storage of the mapping of a permutation to actually be the dict of its two-line notation.
Activity2.3.Flesh out __init__ with input validation.
In order to start building a useful permutation class, we make the assumption that the input has to be in one-line notation. This is easy to change later once we have a better understanding of what we want from our permutation code.
(a)
Implement your algorithm in the AlgoPerm class. Begin by editing the __init__ method of AlgoPerm so that it looks as follows:
def __init__(self, mapping, domain=None):
# Check to see whether mapping provides a valid permutation.
if type(mapping) == dict:
# This is effectively two-line notation. Each value must also be a key.
#
# Change the following line to validate the input!!!
keyset_equals_valueset = False
#
if keyset_equals_valueset:
# This use of '.copy()' has to do with data in memory versus
# the name of a variable.
map_dict = mapping.copy()
else:
raise ValueError("Mapping does not specify valid permutation as dictionary.")
elif type(mapping) == list:
# One-line notation. Have to check that the mapping corresponds to
# the list [1, 2, ..., k] for some k.
#
# Change the following line to validate the input!!!
valid_oneline = False
#
if valid_oneline:
# build the mapping dictionary
map_dict = { }
for i in range(maxx):
map_dict[i+1] = mapping[i]
else:
raise ValueError("Mapping does not specify valid one-line notation.")
elif type(mapping) == tuple:
# Cycle notation. This is tricky! Skip it for now.
raise NotImplementedError("Cannot currently define a permutation from cycle tuples")
else:
raise TypeError(f"Mapping must be list (oneline notation), tuple (cycle notation), or dictionary, not {type(mapping)}.")
#
# We'll rewrite this later:
if domain!=None:
pass
set_domain = set(map_dict.keys())
# Assign the value of map_dict into the self.mapping attribute
self._mapping = map_dict
# Set all attributes other than the canonical data storage.
self._domain = set_domain
If you copied and pasted that into your file, it is likely that you are having errors. Try typing it in by hand instead.
(b)
Correct the two data validation lines from the code.
(c)
In your aam_proj2.py file, test your newly defined and corrected class. Add the following lines to the bottom of the aam_proj2.py file and execute it.
def __repr__(self):
"""Return a string containing the mapping dictionary of an AlgoPerm."""
return str(self._mapping)
If you execute the aam-proj2.py file after making this change, you’ll see that the print statements have a more pleasing output.
Subsection2.2.4Additional methods
In the previous section, we discussed a number of mathematical operations which can be performed on permutations. The first and fundamentally most important operation to define for our AlgoPerm class is the calling method. This is what we mean when we use the \(f(x)\) notation to represent the value assigned by a function named \(f\) to a domain value \(x\text{.}\)
Technology2.2.19.__call__ method.
An object my_obj which is an instance of MyClass can be called using my_obj(x) if and only if the __call__ method is defined in MyClass and x is a valid input.
The arguments to the __call__ method in our AlgoPerm class are simple: the self argument (as always) and one other argument, which we will name other.
Activity2.5.Calling AlgoPerm.
There is a mathematically important reason and a computationally important reason to define this method. Mathematically, the method is important because permutations are functions, and functions are callable. Computationally it is important because we don’t want to have to worry about exactly how the AlgoPerm class is written in order to use it. Specifically, once we write the __call__ method we don’t have to keep track of the AlgoPerm._mapping most of the time, because we can instead use function notation.
(a)
Define a __call__ method in your AlgoPerm class.
def __call__(self, other):
"""Perform self(other)"""
try:
return self._mapping[other]
except KeyError:
raise ValueError(f"{other} is not in the domain of {self}")
(b)
Test your new method in aam_proj2.py by adding print(a(8)) and print(b(31)) lines. Diagnose what occurs and why.
With the ability to use our AlgoPerm objects as functions, the next feature we should define is composition. Recalling that we want to read \(\sigma\after\tau\) as “\(\sigma\) after \(\tau\)”, we define new methods which are not special double-underscore methods.
Activity2.6.AlgoPerm methods for domain and after.
(a)
Define a domain method for AlgoPerm as follows.
def domain(self):
"""Return the set consisting of the domain of self."""
return self._domain
While we could just continue to access the _domain attribute, it is good programming style to not refer directly to attributes, but instead use methods to access their values.
(b)
Define a after method for AlgoPerm, beginning as follows.
def after(self, other):
"""Return the AlgoPerm obtained by composition of self after other."""
if some_error_condition:
# 1. Validate that other is an AlgoPerm
pass
elif some_other_error:
# 2. Validate that the domain of other is a subset of the domain of self
pass
else:
# Otherwise, define an empty new mapping dictionary
new_mapping = { }
# 3. Iterate over all the elements of the domain of other, making the
# correct assignments in new_mapping
#
# 4. Iterate over all the elements of the domain of self which are
# not in the domain of other, making the correct assignments
# in new_mapping
#
# Return the correct AlgoPerm
return AlgoPerm(new_mapping)
(c)
The new method after has several steps described in comments. Finish the code so that the result of print(a.after(b)) in your aam_proj2.py file is {1: 1, 2: 5, 3: 3, 4: 6, 5: 2, 6: 4, 7: 10, 8: 9, 9: 8, 10: 7}. Hint: You should see what methods are available for the set class, by looking at help(set).
(d)
Operator overloading is the fancy name for when we have one symbol (such as *) which must perform multiple tasks in multiple different contexts. All of the double-underscore __methods__ we have been working with are the means by which Python performs operator overloading. Rather than continuing to use after for composition, it becomes much easier to use Python’s multiplication operator * as we use it mathematically.
Overload the * operator for AlgoPerm by defining the following new method.
Since we know it is very important to be consistent with your left and right multiplication, we now note that the left multiplication of self*right is effected using __mul__(self, right) and the right multiplication of left * self is effected using a different method, __rmul__(self, left). There is an order of operations in Python just as in mathematics, and Python checks for a valid left multiplication before checking for a valid right multiplication.
Activity2.7.Inverses of AlgoPerm objects.
Since a permutation is a bijection, an important last tool is to build a inverse method in the AlgoPerm class.
(a)
Finish the following code.
def inverse(self):
"""Return the AlgoPerm which is the inverse of self."""
# Set pairs to be the list of tuples (x, self(x))
pairs = self._mapping.items()
# Create an empty inverse mapping dictionary
inv_mapping = { }
# Iterate through pairs assigning the correct inverse mappings.
#
return AlgoPerm(inv_mapping)
(b)
In your aam_proj2.py file, investigate the difference between a*b.inverse() and (a*b).inverse(). Explain why they should be different, mathematically.
In the next section, we will investigate an application of permutations that makes all this work helpful.
