Python for Everyone!
Oregon Curriculum Network
Playing with permutations (perms) fresh out of the box, with operator overloading already implemented, is best appreciated up front, with any dive into source code to follow.
The main point at first is to see what a perm can do:
In [1]:
from px_class import P
perm = P().shuffle()
print(perm)
m = "this is plaintext"
print("p=", m)
cyphertext = perm(m) # send it over the wire (pretend)
print("c=", cyphertext)
# lets decipher the ciphertext
decoder_ring = ~perm # the undo of perm
print("m=", decoder_ring(cyphertext))
The class below wraps a _code object, a Python dict, and then uses that to implement encrypt and decrypt methods. A simple substitution code is easy to break, based on letter frequency, presuming the original language is known.
Permutations may be thought of as chainable i.e. composable functions, i.e. they multiply. That which may be multiplied, may be powered as well. The group theory notion of "inverse" makes sense in that p * ~p should give back the Identity permutation. The identity permutation carries every element to itself in the same position.
Think of a "do" * "undo" such that an encrypting would pair with a decrypting, returning the original plaintext. That's the work of the Identity permutation as well.
Permutations are at the heart of Group Theory, as we begin to develop a sense of an Abstract Algebra. In this universe, a thing will always pair with an anti-thing (inverses exist) and two things will always multiply to give a third thing (closure). There's an identity thing, its own inverse. Multiplication is associative but in the general case maybe not commutative. In the case of these permutations, it is.
Sometimes these properties get summarized as CAIN, with the pun that commutative groups are Abelian. Cain and Abel, get it?
In [2]:
from px_class import P
p = P().shuffle()
print(p._code)
q = ~p
print(q._code)
In [3]:
p = P().shuffle()
anti_p = ~p
assert p * ~p == ~p * p # commutativity
I = ~p * p # identity
assert I * p == p == p * I
What you see above is operator overloading. Even if you're maybe glazing over as to what it means to invert, or to multiply, what's clear is these to operators have meaning, are being used.
The inverted permutation is a reverse dictionary, undoing the swap with a path back to the start. 'a' maps to 's' but then, in the inverse code, 's' maps right back to 'a'.
To multiply is like to compose two functions, in that for A times B, each key in A points ends up pointing to the corresponding B[A[key]].
In [4]:
p = P().shuffle()
q = P().shuffle()
print('p =', p)
print('q =', q)
r = p * q
print("p['a'] =", p('a'))
print("q[p('a')] =", q[p('a')])
print("r('a') =", r('a'))
That's why multiplying a permutation with its own inverse is the same as "doing nothing" just as the identity permutation does. Any permutation multiplied by I (the identity) results in the same thing.
In [5]:
I = P() # without shuffling, P() returns I
assert I == ~I
q = P().shuffle() # any perm
assert I * q == q == q * I
In [6]:
# %load px_class.py
"""
Last updated Mar 10, 2020
@author: Kirby Urner
(c) MIT License
Fun for Group Theory + Python
https://github.com/4dsolutions/Python5/blob/master/px_class.py
"""
from random import shuffle
from string import ascii_lowercase # all lowercase letters
from functools import reduce
Before diving deeper into Permutations, a couple helper functions will come in handy, that of gcd (greatest common divisor) and lcm (lowest common multiple). These two are related. Furthermore, we would like versions which tackle any number of integer inputs, which we'll call GCD and LCD respectively.
In [7]:
def gcd(a, b):
while b:
b, a = a % b, b
return a
def lcm(a, b):
return int((a * b)/gcd(a, b))
def GCD(*terms):
return reduce(gcd, terms)
def LCM(*terms):
return reduce(lcm, terms)
In [8]:
GCD(25, 50, 15)
Out[8]:
In [9]:
LCM(25, 50, 15)
Out[9]:
In [10]:
class P:
"""
A Permutation
self._code: a dict, is a mapping of iterable elements
to themselves in any order.
start out with Identity, or directly inject the mapping as
a dict or use an inversions table to construct the permutation
"""
def __init__(self,
the_code = None, # direct inject
inv_table = None, # construct
iterable = ascii_lowercase + ' '): # default domain
if the_code:
self._code = the_code
elif inv_table:
values = []
for key in sorted(inv_table, reverse=True):
if inv_table[key] >= len(values):
values.append(key)
else:
values.insert(inv_table[key], key)
self._code = dict(zip(sorted(inv_table), values))
elif iterable:
try:
# create two iterators for zipping together
iter1 = iter(iterable)
iter2 = iter(iterable)
except:
raise TypeError
self._code = dict(zip(iter1, iter2))
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 copied one
newP = P()
# old keys point to new ones
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 __truediv__(self, other):
return self * ~other
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
def inversion_table(self):
invs = {}
invP = ~self
keys = sorted(self._code)
for key in keys:
x = invP[key] # position of key
cnt = 0
for left_of_key in keys: # in order up to position
if left_of_key == x: # none more to left
break
if self._code[left_of_key] > key:
cnt += 1
invs[key] = cnt
return invs
def order(self):
return LCM(*map(len, self.cyclic()))
__len__ = order
def sgn(self):
"""
Wikipedia:
https://en.wikipedia.org/wiki/Parity_of_a_permutation
In practice, in order to determine whether a given
permutation is even or odd, one writes the permutation
as a product of disjoint cycles. The permutation is
odd if and only if this factorization contains an
odd number of even-length cycles.
"""
parity = sum([len(cycle)%2==0
for cycle in self.cyclic()]) % 2
# sign is 1 if parity is even, else -1
return -1 if (parity % 2) else 1 # parity % 2 True if odd
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")
#==========
knuth = {1:5, 2:9, 3:1, 4:8, 5:2, 6:6, 7:4, 8:7, 9:3} # vol 3 pg. 12
expected = {1:2, 2:3, 3:6, 4:4, 5:0, 6:2, 7:2, 8:1, 9:0} # Ibid
k = P(the_code=knuth)
try:
assert k.inversion_table() == expected
print("Fourth Test Succeeds")
except AssertionError:
print("Fourth Test Fails")
#==========
p = P(inv_table = expected)
try:
assert p == k
print("Fifth Test Succeeds")
except AssertionError:
print("Fifth Test Fails")
#==========
p = P().shuffle()
inv = p.inversion_table()
print("Perm:", p._code)
print("Inv table:", inv)
new_p = P(inv_table = inv)
try:
assert p == new_p
print("Sixth Test Succeeds")
except AssertionError:
print("Sixth Test Fails")
#==========
p = P().shuffle()
order = len(p)
sign = p.sgn()
print("Perm:", p._code)
print("Order:", order)
print("Sign:", sign)
try:
inv_p = ~p
assert p.sgn() == inv_p.sgn()
print("Seventh Test Succeeds")
except AssertionError:
print("Seventh Test Fails")
In this first test, lets make sure that any random permutation, times its inverse, gives the Identity permutation...
In [11]:
p = P() # identity permutation
print(dir(p))
p.shuffle()
#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")
Since it makes sense to both power, and invert, we may raise permutations to a negative power. (p ** -1) is another way of saying "give me the inverse"...
In [12]:
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")
Since Permutation p will be able to compute it's own inverse, decrypting the cyphertext is a snap...
In [13]:
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")
In [14]:
knuth = {1:5, 2:9, 3:1, 4:8, 5:2, 6:6, 7:4, 8:7, 9:3} # vol 3 pg. 12
expected = {1:2, 2:3, 3:6, 4:4, 5:0, 6:2, 7:2, 8:1, 9:0} # Ibid
k = P(the_code=knuth)
try:
assert k.inversion_table() == expected
print("Fourth Test Succeeds")
except AssertionError:
print("Fourth Test Fails")
Lets make sure that, given the derived inversion table for the Permutation named knuth, we're able to regenerate knuth upon initialization...
In [15]:
p = P(inv_table = expected)
try:
assert p == k
print("Fifth Test Succeeds")
except AssertionError:
print("Fifth Test Fails")
Next, given any random permutation, lets make sure we're able to reconstruct it from its inversion table. The only difference from the test above is we're using a random permutation versus the one given on page 12 in volume 3 of The Art of Computer Programming.
In [16]:
p = P().shuffle()
inv = p.inversion_table()
print("Perm:", p._code)
print("Inv table:", inv)
new_p = P(inv_table = inv)
try:
assert p == new_p
print("Sixth Test Succeeds")
except AssertionError:
print("Sixth Test Fails")
Finally, we should talk about the order and the parity of a permutation.
Permutations define subgroups with a specific number of unique elements, which we may define as the order of that permutation. A permutation raised to its own order, as a power, cycles around to where it started, meaning the resulting permutation is the identity permutation.
The sign of a permutation depends on the parity (even or odd) of the number of transpositions it would take, to express the same permutation. An even number of transpositions or no transpositions at all, have a sign of positive 1. Odd numbers of transpositions define permutations of negative sign which is likewise expressed as -1.
The identity permutation is even (no transpositions, or an even number that end up self canceling) and only the set of even permutations defines a subgroup of the total space. The odd permutations define a coset in the total space.
In [17]:
p = P().shuffle()
order = len(p)
sign = p.sgn()
print("Perm:", p._code)
print("Order:", order)
print("Sign:", sign)
try:
inv_p = ~p
assert p.sgn() == inv_p.sgn()
assert P().sgn() == 1 # identity is even
print("Seventh Test Succeeds")
except AssertionError:
print("Seventh Test Fails")