Permutations


Python for Everyone!
Oregon Curriculum Network

Playing with Cyphers

Suggested Andragogy

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))


P class: (('a', 'x'), ('b', 'k'), ('c', 'e'))...
p= this is plaintext
c= bzquoquopnxqgbsfb
m= this is plaintext

Operator Overloading in Python

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)


{'a': 'y', 'b': 'c', 'c': 'd', 'd': 'j', 'e': 'q', 'f': 'x', 'g': 'i', 'h': 'v', 'i': 'w', 'j': 'l', 'k': 'o', 'l': 'e', 'm': 'g', 'n': 'h', 'o': 'r', 'p': 'n', 'q': ' ', 'r': 'k', 's': 's', 't': 'a', 'u': 'b', 'v': 'u', 'w': 'p', 'x': 'm', 'y': 'f', 'z': 'z', ' ': 't'}
{'y': 'a', 'c': 'b', 'd': 'c', 'j': 'd', 'q': 'e', 'x': 'f', 'i': 'g', 'v': 'h', 'w': 'i', 'l': 'j', 'o': 'k', 'e': 'l', 'g': 'm', 'h': 'n', 'r': 'o', 'n': 'p', ' ': 'q', 'k': 'r', 's': 's', 'a': 't', 'b': 'u', 'u': 'v', 'p': 'w', 'm': 'x', 'f': 'y', 'z': 'z', 't': ' '}

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'))


p = P class: (('a', 'e'), ('b', 'q'), ('c', 'c'))...
q = P class: (('a', 'r'), ('b', 'c'), ('c', 'k'))...
p['a']    = e
q[p('a')] = v
r('a')    = v

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

Cyclic Notation

Cyclic notation is a clever way of representing a permutation as a tuple of tuples, whereas every permuation likewise has a unique "inversion table" defined below by Knuth.


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]:
5

In [9]:
LCM(25, 50, 15)


Out[9]:
150

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")


First Test Succeeds
Second Test Succeeds
Plain:   able was i ere i saw elba
Cipher:  q hybtqjbvbyrybvbjqtbyh q
Third Test Succeeds
Fourth Test Succeeds
Fifth Test Succeeds
Perm: {'a': 'f', 'b': 'y', 'c': 't', 'd': 'k', 'e': 'n', 'f': ' ', 'g': 'e', 'h': 'g', 'i': 'b', 'j': 'i', 'k': 'm', 'l': 'z', 'm': 'd', 'n': 'u', 'o': 'r', 'p': 'p', 'q': 'h', 'r': 'w', 's': 'c', 't': 's', 'u': 'x', 'v': 'j', 'w': 'a', 'x': 'l', 'y': 'v', 'z': 'o', ' ': 'q'}
Inv table: {' ': 6, 'a': 22, 'b': 8, 'c': 17, 'd': 11, 'e': 6, 'f': 1, 'g': 5, 'h': 11, 'i': 5, 'j': 13, 'k': 3, 'l': 12, 'm': 4, 'n': 3, 'o': 11, 'p': 6, 'q': 0, 'r': 4, 's': 5, 't': 1, 'u': 2, 'v': 4, 'w': 2, 'x': 2, 'y': 0, 'z': 0}
Sixth Test Succeeds
Perm: {'a': 'g', 'b': 'y', 'c': 'p', 'd': 'r', 'e': 'a', 'f': 'v', 'g': ' ', 'h': 'c', 'i': 'f', 'j': 'd', 'k': 'x', 'l': 'i', 'm': 's', 'n': 'n', 'o': 'j', 'p': 'w', 'q': 'h', 'r': 'u', 's': 'b', 't': 'm', 'u': 't', 'v': 'z', 'w': 'e', 'x': 'q', 'y': 'o', 'z': 'l', ' ': 'k'}
Order: 110
Sign: -1
Seventh Test Succeeds

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")


['__call__', '__class__', '__delattr__', '__dict__', '__dir__', '__doc__', '__eq__', '__format__', '__ge__', '__getattribute__', '__getitem__', '__gt__', '__hash__', '__init__', '__init_subclass__', '__invert__', '__le__', '__len__', '__lt__', '__module__', '__mul__', '__ne__', '__new__', '__pow__', '__reduce__', '__reduce_ex__', '__repr__', '__setattr__', '__sizeof__', '__str__', '__subclasshook__', '__truediv__', '__weakref__', '_code', 'cyclic', 'decrypt', 'encrypt', 'inversion_table', 'order', 'sgn', 'shuffle']
First Test Succeeds

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")


Second Test Succeeds

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")


Plain:   able was i ere i saw elba
Cipher:  rfcnbjrobebnmnbeborjbncfr
Third Test Succeeds

Inversion Table Notation

"The inversion table B1 B2 ... Bn of the permutation A1, A2 ... An is obtained by letting Bj be the number of elements to the left of j that are greater than j." -- Donald E. Knuth


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")


Fourth Test Succeeds

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")


Fifth Test Succeeds

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")


Perm: {'a': 'b', 'b': 't', 'c': 'l', 'd': 'f', 'e': 'n', 'f': 's', 'g': 'd', 'h': 'm', 'i': 'q', 'j': 'p', 'k': 'k', 'l': 'j', 'm': 'o', 'n': 'w', 'o': 'x', 'p': 'h', 'q': 'u', 'r': 'c', 's': 'y', 't': 'r', 'u': 'g', 'v': ' ', 'w': 'v', 'x': 'i', 'y': 'z', 'z': 'a', ' ': 'e'}
Inv table: {' ': 22, 'a': 25, 'b': 1, 'c': 17, 'd': 6, 'e': 0, 'f': 2, 'g': 16, 'h': 12, 'i': 16, 'j': 8, 'k': 7, 'l': 1, 'm': 3, 'n': 1, 'o': 4, 'p': 3, 'q': 2, 'r': 6, 's': 1, 't': 0, 'u': 2, 'v': 3, 'w': 0, 'x': 0, 'y': 0, 'z': 0}
Sixth Test Succeeds

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 [ ]:
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")