[Edu-sig] Group Theory for Girl Scouts (and Boys too)

[kirby urner]

One of my favorite topics in mathematics which I think is accessible to
kids, is that of "permutations" treated as objects, and made to "compose".
To this I affix the notion of "substitution code" or "club house code", one
of the simplest ciphers imaginable, and we're off, studying Group Theory.
Then add Python.

Rewind:  what's found in a traditional math book around here?  A mapping,
of integers to integers usually, and what's called cyclic notation.
Suppose I have the digits 0 through 9, often used, and my Permutation P
takes the 0 to 3, 1 to 5, 2 to 7, 3 to 8, 4 to 9, 5 to... it starts to get
to where you want two columns of numbers, with arrows in between.

In Python we could just go like this:

import random

def makeperm(someset):
    thecopy = list(someset)
    random.shuffle(thecopy)
    return dict(zip(someset,thecopy))

digits = "0123456789"

print("P1: ",makeperm(digits))
print("P2: ",makeperm(digits))

There's some playfulness here, with duck typing, in that the parameter name
suggests a set, yet we pass a string, then work with listifications.  This
allows more types of input, yet the output should always be:  a dict, a
mapping, a permutation.  Running it now, I get:

P1:  {'1': '6', '0': '1', '3': '8', '2': '5', '5': '3', '4': '0', '7': '2',
'6': '4', '9': '9', '8': '7'}
P2:  {'1': '0', '0': '5', '3': '6', '2': '4', '5': '8', '4': '3', '7': '2',
'6': '7', '9': '9', '8': '1'}

So what's cyclic notation again?  I hadn't gotten that far, as we needed an
easy way to get permutations.  Thanks Python.

Lets work on P1.  You start a tuple going (1, 6, 4, 0).  See what I did?  I
started with 1, arbitrarily and found it maps to 6.  Then I looked up 6 and
found it mapped to 4.  I keep following that trail until I either get back
to where I started, meaning the last element is deemed to connect to the
first.  It's a circle, a cycle.  But maybe we're not done.  2 is not
mentioned so lets start there.  2 maps to 5 maps to 3 maps to 8 maps to 7
maps to 2.  Another circle:  (2, 5, 3, 8, 7).  Anyone missing?  9, where's
9.  9 maps to itself, so (9,) -- using Python notation.  And we're done:
P1 may be expressed as ((0, 1, 6, 4), (2, 5, 3, 8, 7), (9,)).  I can start
with the lowest number in each cycle and sort the cycles by lowest
leftmost, if I want a canonical order.  The above is canonical and unique
for P1.

Rather than work on P2, I'd say lets write a Python program to eat a
permutation and spit out a tuple of tuples, that same Permutation in cyclic
notation.  Then we could build a Permutation class, with cyclic output in
the __repr__ (maybe).  So many things we could do, and we haven't even used
letters yet.

When we do get to letters, I want to emphasis str.maketrans and
str.translate as efficient for our cause.  makeperm above will already work
with string.ascii_lowercase, plus I always add the space as a character.
The resulting dict is already a translation table suitable for our doing
our substitution code.

import random, string

def makeperm(someset):
    thecopy = list(someset)
    random.shuffle(thecopy)
    return dict(zip(someset,thecopy))

alpha = string.ascii_lowercase + " " # 26 letters + space

P1 = makeperm(alpha)
T1 = str.maketrans("".join(P1.keys()), "".join(P1.values()))
invT1 = str.maketrans("".join(P1.values()), "".join(P1.keys()))

m = "the rain in spain stays mainly in the plain"

c = m.translate(T1)  # plaintext -> ciphertext

print("Plaintext:  ", m)
print("Ciphertext: ", c)

decoded = c.translate(invT1)
print("Decoded:    ", decoded)

I'd say we've hit gold:

Plaintext:   the rain in spain stays mainly in the plain
Ciphertext:  xajehroieoiefcroiefxrbfelroiwbeoiexajecwroi
Decoded:     the rain in spain stays mainly in the plain

For a lot of students, looping in a Clubhouse Code aspect counts as an
"application" and grounds our Group Theory in something "meaningful".

I've also sneaked in invT1, the inverse of translation T1, in turn
developed from permutation P1.  invP1 is the reverse lookup dict, where
phone numbers take you to names instead of names to phone numbers (analogy).

This is where the class version of P (Permutation) comes in handy, because
we want to implement __mul__ as Permutation composition.  P1 * invP1 is
going to be the identity mapping, where each element is mapped to itself.
I = P * ~P.  We're into it now.  We've got the properties of a Group:
Closure, Associativity, Inverse (~P) and a Neutral element (I), which
spells CAIN for the mnemonic enthusiasts among you.

Group Theory boils down to permutations, that's one of the theorems.

Plus we learn a lot of Python this way.

Kirby
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/edu-sig/attachments/20130718/5f7ad7fb/attachment.html>