[Edu-sig] Permutations with Python
kirby urner
kirby.urner at gmail.com
Wed Nov 18 17:59:33 EST 2015
My long history on this edu-sig listserv @ python.org has included an
agenda around STEM reform. I've wanted to change US K-16 by displacing
math track scientific calculators with true REPLs, then altering the math
content based on the new freedom a REPL provides.
Using the I-Python REPL:
In [129]: from px_class import *
In [130]: p = P(range(10)).shuffle()
In [131]: p
Out[131]: P class: ((0, 6), (1, 4), (2, 0))...
In [132]: p._code
Out[132]: {0: 6, 1: 4, 2: 0, 3: 3, 4: 8, 5: 9, 6: 1, 7: 5, 8: 2, 9: 7}
In [133]: p.cyclic()
Out[133]: ((0, 6, 1, 4, 8, 2), (3,), (5, 9, 7))
My __repr__ for the P class actually uses ... i.e. this is unedited
output. The idea of a Permutation (P) is very primitive: a mapping of
elements to themselves i.e. a dict where keys and values are the same
elements, but with values in any order.
The identity permutation maps every element to itself. p= P() starts out
with the identity permutation, but then any p instance has a .shuffle
method to return a new instance with a permuted version of the original
dict. p = P().shuffle() creates a random instance in one step.
By default, my Permutations use the lowercase alphabet plus space, to form
a 27-element self._code (the dict). The encrypt and decrypt methods may be
fed ordinary strings of lowercase letters.
From:
p = P().shuffle()
s = "able was i ere i saw elba"
c = p(s)
print("Plain: ", s)
print("Cipher: ", c)
try:
assert p.decrypt(c) == s
print("Third Test Succeeds")
except AssertionError:
print("Third Test Fails")
comes the output:
Plain: able was i ere i saw elba
Cipher: fp vnufcnlnvjvnlncfunv pf
Third Test Succeeds
I think it's an economic reality the curriculum publishers do not want to
compete with their own products.
Computer science in high school has, historically speaking, been a
back-of-the-bus second-class citizen, earning only "elective credit" for
its course takers, if there's more than a "computer club" (i.e. if the
content is not extra-curricular), plus a chance to pass the AP test. That
made sense until the languages got so friendly and easy to use.
Now that we're redoing the mathematics track itself, in light of these
changes in technology, we have an opportunity to bring in new topics such
as Group Theory and Euclid's Algorithm (EA) for the greatest common divisor
(GCD).
With GCD in the picture, we're ready for relative primality and therefore
concepts of totative / totient. I've harped on these topics before.
They're simple and accessible, pre-college, not much background required.
Unless one grasps the concept of Group, there's no getting Field, with
Group, Ring and Field being fundamental algebraic structures. There's no
arguing these concepts are irrelevant, even in K-12.
Permutations may be multiplied (the operation), plus each has an inverse,
defined as the key->value mapping that goes the other way i.e. the dict is
inverted. How does one invert a dictionary in Python code? Good exercise,
so again we're not just earning math credit, we're improving our Python
skills.
The properties of a Group are sometimes given as 'CAIN':
*(C)* Closure: p = P().shuffle(); q = P().shuffle(); p * q is always
another P.
*(A)* Associativity: (p * q) * r == p * (q * r) for all Permutations p,
q, r
*(I)* Inverse: every p = P().shuffle() has an inverse such that p * ~p ==
p ** 0
*(N)* Neutral element: every group has an Identity element with respect to
its operation (*) such that p * P() == P() * p == p.
I'm currently teaching a course in Python for the State of California. My
adult students join me in real time for 10 four hour segments. I've just
completed my fourth. We're coding classes (types) already, were looking at
simple class constructs from Day One. I've suggested they adopt the
mindset of a future high school student, privileged to have a real REPL.
Last night, for a lab, I had the class tackle adding __pow__ to the P
class, given I'd already implemented __mul__. Playing with a Permutation
class is just a tiny fraction of all we do. I spiral back to it in each
session as I introduce new Python features.
Today, I added more methods to the Permutation so I can simply lecture on
them tomorrow evening and invite downloading and reuse.
Here's the source code as of now, pretty well tested:
# -*- coding: utf-8 -*-
"""
Created on Tue Nov 10 17:39:09 2015
@author: Kirby Urner
(c) MIT License (fine to reuse / alter / share)
Fun for Group Theory + Python
"""
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 + ' '):
"""
start out with Identity
"""
self._code = dict(zip(iterable, iterable))
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
newP = P()
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 __getitem__(self, key):
return self._code.get(key, None)
def __repr__(self):
return "P class: " + str(tuple(self._code.items())[:3]) + "..."
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 __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 __pow__(self, exp):
"""
multiply self * self the right number of times
"""
if exp == 0:
output = P()
else:
output = self
for x in range(1, abs(exp)):
output *= self
if exp < 0:
output = ~output
return output
def __call__(self, s):
"""
another way to encrypt
"""
return self.encrypt(s)
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._code == other._code
"""
return self._code == other._code
if __name__ == "__main__":
p = P() # identity permutation
new_p = p.shuffle()
inv_p = ~new_p
try:
assert p == inv_p * new_p # should be True
print("First Test Succeeds")
except AssertionError:
print("First Test Fails")
#==========
p = P().shuffle()
try:
assert p ** -1 == ~p
assert p ** -2 == ~(p * p)
assert p ** -2 == (~p * ~p)
print("Second Test Succeeds")
except AssertionError:
print("Second Test Fails")
#==========
p = P().shuffle()
s = "able was i ere i saw elba"
c = p(s)
print("Plain: ", s)
print("Cipher: ", c)
try:
assert p.decrypt(c) == s
print("Third Test Succeeds")
except AssertionError:
print("Third Test Fails")
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/edu-sig/attachments/20151118/66bd0dc6/attachment-0001.html>
More information about the Edu-sig
mailing list