Group Theory for Girl Scouts (and Boys too)
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
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.
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'} def get_cyclic(codedict): """ Return Permutation dict as a tuple of cyclic tuples, e.g. (('A','R','C'),('D','Q')...) """ dictkeys = list(codedict.keys()) result = [] for i in list(dictkeys): # using copy of dictkeys newtuple = () if i in dictkeys: initval,nextval = i,i while True: newtuple += (nextval,) dictkeys.remove(nextval) nextval = codedict[nextval] if nextval==initval: # cycle complete break result.append(newtuple) return tuple(result) print(get_cyclic(P1)) print(get_cyclic(P2)) Running.... (('1', '6', '4', '0'), ('3', '8', '7', '2', '5'), ('9',)) (('1', '0', '5', '8'), ('3', '6', '7', '2', '4'), ('9',)) Process finished with exit code 0 Kirby
participants (2)
-
kirby urner
-
Kirby Urner