{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "Python for Everyone!
[Oregon Curriculum Network](http://4dsolutions.net/ocn/)\n", "\n", "## Playing with Cyphers\n", "\n", "### Suggested Andragogy\n", "\n", "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.\n", "\n", "The main point at first is to see what a perm can do:" ] }, { "cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "P class: (('a', 'q'), ('b', 't'), ('c', 'b'))...\n", "p= this is plaintext\n", "c= nesjxsjxviqsynzrn\n", "m= this is plaintext\n" ] } ], "source": [ "from px_class import P\n", "perm = P().shuffle()\n", "print(perm)\n", "m = \"this is plaintext\"\n", "print(\"p=\", m)\n", "cyphertext = perm(m) # send it over the wire (pretend)\n", "print(\"c=\", cyphertext)\n", "# lets decipher the ciphertext\n", "decoder_ring = ~perm # the undo of perm\n", "print(\"m=\", decoder_ring(cyphertext))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Operator Overloading in Python\n", "\n", "\n", "\n", "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.\n", "\n", "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.\n", "\n", "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.\n", "\n", "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.\n", "\n", "Sometimes these properties get summarized as CAIN, with the pun that commutative groups are Abelian. Cain and Abel, get it?" ] }, { "cell_type": "code", "execution_count": 2, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "{'a': 'n', 'b': 'j', 'c': 'w', 'd': 'o', 'e': 'b', 'f': 'g', 'g': 't', 'h': 'x', 'i': 'f', 'j': 'e', 'k': 'p', 'l': 'k', 'm': 'l', 'n': 'u', 'o': 'm', 'p': ' ', 'q': 'q', 'r': 'c', 's': 'a', 't': 'v', 'u': 's', 'v': 'i', 'w': 'r', 'x': 'z', 'y': 'd', 'z': 'y', ' ': 'h'}\n", "{'n': 'a', 'j': 'b', 'w': 'c', 'o': 'd', 'b': 'e', 'g': 'f', 't': 'g', 'x': 'h', 'f': 'i', 'e': 'j', 'p': 'k', 'k': 'l', 'l': 'm', 'u': 'n', 'm': 'o', ' ': 'p', 'q': 'q', 'c': 'r', 'a': 's', 'v': 't', 's': 'u', 'i': 'v', 'r': 'w', 'z': 'x', 'd': 'y', 'y': 'z', 'h': ' '}\n" ] } ], "source": [ "from px_class import P\n", "p = P().shuffle()\n", "print(p._code)\n", "q = ~p\n", "print(q._code)" ] }, { "cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [], "source": [ "p = P().shuffle()\n", "anti_p = ~p\n", "assert p * ~p == ~p * p # commutativity\n", "I = ~p * p # identity\n", "assert I * p == p == p * I" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "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.\n", "\n", "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'.\n", "\n", "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]]```." ] }, { "cell_type": "code", "execution_count": 4, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "p = P class: (('a', 'l'), ('b', 'r'), ('c', 'f'))...\n", "q = P class: (('a', 'x'), ('b', 'q'), ('c', 'o'))...\n", "p['a'] = l\n", "q[p('a')] = e\n", "r('a') = e\n" ] } ], "source": [ "p = P().shuffle()\n", "q = P().shuffle()\n", "print('p =', p)\n", "print('q =', q)\n", "r = p * q\n", "print(\"p['a'] =\", p('a')) \n", "print(\"q[p('a')] =\", q[p('a')]) \n", "print(\"r('a') =\", r('a'))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "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." ] }, { "cell_type": "code", "execution_count": 5, "metadata": {}, "outputs": [], "source": [ "I = P() # without shuffling, P() returns I\n", "assert I == ~I\n", "q = P().shuffle() # any perm\n", "assert I * q == q == q * I" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Cyclic Notation\n", "\n", "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." ] }, { "cell_type": "code", "execution_count": 6, "metadata": {}, "outputs": [], "source": [ "# %load px_class.py\n", "\"\"\"\n", "Last updated Mar 10, 2020\n", "\n", "@author: Kirby Urner\n", "(c) MIT License\n", "\n", "Fun for Group Theory + Python\n", "https://github.com/4dsolutions/Python5/blob/master/px_class.py\n", "\n", "\"\"\"\n", "\n", "from random import shuffle \n", "from string import ascii_lowercase # all lowercase letters\n", "from functools import reduce" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "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." ] }, { "cell_type": "code", "execution_count": 7, "metadata": {}, "outputs": [], "source": [ "def gcd(a, b):\n", " while b:\n", " b, a = a % b, b\n", " return a\n", "\n", "def lcm(a, b):\n", " return int((a * b)/gcd(a, b))\n", "\n", "def GCD(*terms):\n", " return reduce(gcd, terms)\n", "\n", "def LCM(*terms):\n", " return reduce(lcm, terms)" ] }, { "cell_type": "code", "execution_count": 8, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "5" ] }, "execution_count": 8, "metadata": {}, "output_type": "execute_result" } ], "source": [ "GCD(25, 50, 15)" ] }, { "cell_type": "code", "execution_count": 9, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "150" ] }, "execution_count": 9, "metadata": {}, "output_type": "execute_result" } ], "source": [ "LCM(25, 50, 15)" ] }, { "cell_type": "code", "execution_count": 10, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "First Test Succeeds\n", "Second Test Succeeds\n", "Plain: able was i ere i saw elba\n", "Cipher: zmujekzbeaejrjeaebzkejumz\n", "Third Test Succeeds\n", "Fourth Test Succeeds\n", "Fifth Test Succeeds\n", "Perm: {'a': 'p', 'b': 'g', 'c': 'j', 'd': 'm', 'e': 'd', 'f': 'c', 'g': 's', 'h': 'v', 'i': ' ', 'j': 'q', 'k': 'l', 'l': 'r', 'm': 'z', 'n': 'k', 'o': 'w', 'p': 'o', 'q': 'y', 'r': 'i', 's': 'h', 't': 'f', 'u': 'a', 'v': 'x', 'w': 'n', 'x': 'b', 'y': 'u', 'z': 'e', ' ': 't'}\n", "Inv table: {' ': 9, 'a': 20, 'b': 22, 'c': 6, 'd': 5, 'e': 21, 'f': 17, 'g': 2, 'h': 15, 'i': 14, 'j': 2, 'k': 9, 'l': 6, 'm': 2, 'n': 11, 'o': 8, 'p': 1, 'q': 3, 'r': 3, 's': 1, 't': 0, 'u': 5, 'v': 0, 'w': 1, 'x': 2, 'y': 1, 'z': 0}\n", "Sixth Test Succeeds\n", "Perm: {'a': 'u', 'b': 'f', 'c': 'd', 'd': 's', 'e': 'g', 'f': ' ', 'g': 'z', 'h': 'p', 'i': 't', 'j': 'c', 'k': 'b', 'l': 'r', 'm': 'o', 'n': 'e', 'o': 'w', 'p': 'n', 'q': 'q', 'r': 'k', 's': 'h', 't': 'a', 'u': 'i', 'v': 'j', 'w': 'y', 'x': 'l', 'y': 'm', 'z': 'x', ' ': 'v'}\n", "Order: 36\n", "Sign: -1\n", "Seventh Test Succeeds\n" ] } ], "source": [ "class P:\n", " \"\"\"\n", " A Permutation\n", " \n", " self._code: a dict, is a mapping of iterable elements \n", " to themselves in any order.\n", "\n", " start out with Identity, or directly inject the mapping as\n", " a dict or use an inversions table to construct the permutation\n", " \"\"\" \n", "\n", " def __init__(self, \n", " the_code = None, # direct inject\n", " inv_table = None, # construct \n", " iterable = ascii_lowercase + ' '): # default domain\n", "\n", " if the_code:\n", " self._code = the_code\n", " \n", " elif inv_table:\n", " values = []\n", " for key in sorted(inv_table, reverse=True):\n", " if inv_table[key] >= len(values):\n", " values.append(key)\n", " else:\n", " values.insert(inv_table[key], key)\n", " self._code = dict(zip(sorted(inv_table), values))\n", " \n", " elif iterable: \n", " try:\n", " # create two iterators for zipping together\n", " iter1 = iter(iterable)\n", " iter2 = iter(iterable)\n", " except:\n", " raise TypeError\n", " \n", " self._code = dict(zip(iter1, iter2))\n", " \n", " def shuffle(self):\n", " \"\"\"\n", " return a random permutation of this permutation\n", " \"\"\"\n", " # use shuffle\n", " # something like\n", " the_keys = list(self._code.keys()) # grab keys\n", " shuffle(the_keys) # shuffles copied one\n", " newP = P()\n", " # old keys point to new ones\n", " newP._code = dict(zip(self._code.keys(), the_keys))\n", " return newP\n", " \n", " def encrypt(self, plain):\n", " \"\"\"\n", " turn plaintext into cyphertext using self._code\n", " \"\"\"\n", " output = \"\" # empty string\n", " for c in plain:\n", " output = output + self._code.get(c, c) \n", " return output\n", " \n", " def decrypt(self, cypher):\n", " \"\"\"\n", " Turn cyphertext into plaintext using ~self\n", " \"\"\"\n", " reverse_P = ~self # invert me!\n", " output = \"\"\n", " for c in cypher:\n", " output = output + reverse_P._code.get(c, c)\n", " return output\n", " \n", " def __getitem__(self, key):\n", " return self._code.get(key, None)\n", " \n", " def __repr__(self):\n", " return \"P class: \" + str(tuple(self._code.items())[:3]) + \"...\"\n", "\n", " def cyclic(self):\n", " \"\"\"\n", " cyclic notation, a compact view of a group\n", " \"\"\"\n", " output = []\n", " the_dict = self._code.copy()\n", " while the_dict:\n", " start = tuple(the_dict.keys())[0]\n", " the_cycle = [start]\n", " the_next = the_dict.pop(start)\n", " while the_next != start:\n", " the_cycle.append(the_next)\n", " the_next = the_dict.pop(the_next)\n", " output.append(tuple(the_cycle))\n", " return tuple(output)\n", "\n", " def __mul__(self, other): \n", " \"\"\"\n", " look up my keys to get values that serve\n", " as keys to get others \"target\" values\n", " \"\"\"\n", " new_code = {}\n", " for c in self._code: # going through my keys\n", " target = other._code[ self._code[c] ]\n", " new_code[c] = target\n", " new_P = P(' ') \n", " new_P._code = new_code\n", " return new_P\n", " \n", " def __truediv__(self, other):\n", " return self * ~other\n", " \n", " def __pow__(self, exp):\n", " \"\"\"\n", " multiply self * self the right number of times\n", " \"\"\"\n", " if exp == 0:\n", " output = P()\n", " else:\n", " output = self\n", "\n", " for x in range(1, abs(exp)):\n", " output *= self\n", " \n", " if exp < 0:\n", " output = ~output\n", " \n", " return output\n", "\n", " def __call__(self, s): \n", " \"\"\"\n", " another way to encrypt\n", " \"\"\"\n", " return self.encrypt(s) \n", "\n", " def __invert__(self):\n", " \"\"\"\n", " create new P with reversed dict\n", " \"\"\"\n", " newP = P(' ')\n", " newP._code = dict(zip(self._code.values(), self._code.keys()))\n", " return newP\n", " \n", " def __eq__(self, other):\n", " \"\"\"\n", " are these permutation the same? \n", " Yes if self._code == other._code\n", " \"\"\"\n", " return self._code == other._code\n", " \n", " def inversion_table(self):\n", " invs = {}\n", " invP = ~self\n", " keys = sorted(self._code)\n", " for key in keys:\n", " x = invP[key] # position of key\n", " cnt = 0\n", " for left_of_key in keys: # in order up to position\n", " if left_of_key == x: # none more to left\n", " break\n", " if self._code[left_of_key] > key:\n", " cnt += 1\n", " invs[key] = cnt\n", " return invs\n", " \n", " def order(self):\n", " return LCM(*map(len, self.cyclic()))\n", " \n", " __len__ = order\n", " \n", " def sgn(self):\n", " \"\"\"\n", " Wikipedia: \n", " https://en.wikipedia.org/wiki/Parity_of_a_permutation\n", " In practice, in order to determine whether a given \n", " permutation is even or odd, one writes the permutation \n", " as a product of disjoint cycles. The permutation is \n", " odd if and only if this factorization contains an \n", " odd number of even-length cycles.\n", " \"\"\"\n", " parity = sum([len(cycle)%2==0 \n", " for cycle in self.cyclic()]) % 2\n", " # sign is 1 if parity is even, else -1\n", " return -1 if (parity % 2) else 1 # parity % 2 True if odd\n", " \n", "if __name__ == \"__main__\":\n", " p = P() # identity permutation\n", " new_p = p.shuffle()\n", " inv_p = ~new_p \n", " try:\n", " assert p == inv_p * new_p # should be True\n", " print(\"First Test Succeeds\")\n", " except AssertionError:\n", " print(\"First Test Fails\")\n", " #========== \n", " p = P().shuffle()\n", " try:\n", " assert p ** -1 == ~p\n", " assert p ** -2 == ~(p * p)\n", " assert p ** -2 == (~p * ~p)\n", " print(\"Second Test Succeeds\")\n", " except AssertionError:\n", " print(\"Second Test Fails\")\n", " #========== \n", " p = P().shuffle()\n", " s = \"able was i ere i saw elba\"\n", " c = p(s)\n", " print(\"Plain: \", s)\n", " print(\"Cipher: \", c)\n", " try:\n", " assert p.decrypt(c) == s\n", " print(\"Third Test Succeeds\")\n", " except AssertionError:\n", " print(\"Third Test Fails\")\n", " #========== \n", " knuth = {1:5, 2:9, 3:1, 4:8, 5:2, 6:6, 7:4, 8:7, 9:3} # vol 3 pg. 12\n", " expected = {1:2, 2:3, 3:6, 4:4, 5:0, 6:2, 7:2, 8:1, 9:0} # Ibid\n", " k = P(the_code=knuth)\n", " try: \n", " assert k.inversion_table() == expected\n", " print(\"Fourth Test Succeeds\")\n", " except AssertionError:\n", " print(\"Fourth Test Fails\")\n", " #========== \n", " p = P(inv_table = expected)\n", " try: \n", " assert p == k\n", " print(\"Fifth Test Succeeds\")\n", " except AssertionError:\n", " print(\"Fifth Test Fails\")\n", " #========== \n", " p = P().shuffle()\n", " inv = p.inversion_table()\n", " print(\"Perm:\", p._code)\n", " print(\"Inv table:\", inv)\n", " new_p = P(inv_table = inv)\n", " try: \n", " assert p == new_p\n", " print(\"Sixth Test Succeeds\")\n", " except AssertionError:\n", " print(\"Sixth Test Fails\") \n", " #========== \n", " p = P().shuffle()\n", " order = len(p)\n", " sign = p.sgn()\n", " print(\"Perm:\", p._code)\n", " print(\"Order:\", order)\n", " print(\"Sign:\", sign)\n", " try: \n", " inv_p = ~p\n", " assert p.sgn() == inv_p.sgn()\n", " print(\"Seventh Test Succeeds\")\n", " except AssertionError:\n", " print(\"Seventh Test Fails\") " ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "In this first test, lets make sure that any random permutation, times its inverse, gives the Identity permutation..." ] }, { "cell_type": "code", "execution_count": 11, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "['__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']\n", "First Test Succeeds\n" ] } ], "source": [ "p = P() # identity permutation\n", "print(dir(p))\n", "p.shuffle()\n", "#new_p = p.shuffle()\n", "#inv_p = ~new_p \n", "try:\n", " #assert p == inv_p * new_p # should be True\n", " print(\"First Test Succeeds\")\n", "except AssertionError:\n", " print(\"First Test Fails\")" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "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\"..." ] }, { "cell_type": "code", "execution_count": 12, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Second Test Succeeds\n" ] } ], "source": [ "p = P().shuffle()\n", "try:\n", " assert p ** -1 == ~p\n", " assert p ** -2 == ~(p * p)\n", " assert p ** -2 == (~p * ~p)\n", " print(\"Second Test Succeeds\")\n", "except AssertionError:\n", " print(\"Second Test Fails\")" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Since Permutation p will be able to compute it's own inverse, decrypting the cyphertext is a snap..." ] }, { "cell_type": "code", "execution_count": 13, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Plain: able was i ere i saw elba\n", "Cipher: raiucvrycmcuwucmcyrvcuiar\n", "Third Test Succeeds\n" ] } ], "source": [ "p = P().shuffle()\n", "s = \"able was i ere i saw elba\"\n", "c = p(s)\n", "print(\"Plain: \", s)\n", "print(\"Cipher: \", c)\n", "try:\n", " assert p.decrypt(c) == s\n", " print(\"Third Test Succeeds\")\n", "except AssertionError:\n", " print(\"Third Test Fails\")" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Inversion Table Notation\n", "\n", "\"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\n", "\n", "![Knuth quote](https://c8.staticflickr.com/9/8408/29639707343_ab1df95f9e_z.jpg)" ] }, { "cell_type": "code", "execution_count": 14, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Fourth Test Succeeds\n" ] } ], "source": [ "knuth = {1:5, 2:9, 3:1, 4:8, 5:2, 6:6, 7:4, 8:7, 9:3} # vol 3 pg. 12\n", "expected = {1:2, 2:3, 3:6, 4:4, 5:0, 6:2, 7:2, 8:1, 9:0} # Ibid\n", "k = P(the_code=knuth)\n", "try: \n", " assert k.inversion_table() == expected\n", " print(\"Fourth Test Succeeds\")\n", "except AssertionError:\n", " print(\"Fourth Test Fails\")" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Lets make sure that, given the derived inversion table for the Permutation named *knuth*, we're able to regenerate *knuth* upon initialization..." ] }, { "cell_type": "code", "execution_count": 15, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Fifth Test Succeeds\n" ] } ], "source": [ "p = P(inv_table = expected)\n", "try: \n", " assert p == k\n", " print(\"Fifth Test Succeeds\")\n", "except AssertionError:\n", " print(\"Fifth Test Fails\")" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "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*." ] }, { "cell_type": "code", "execution_count": 16, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Perm: {'a': 'p', 'b': 'r', 'c': 'z', 'd': 's', 'e': 'x', 'f': 'a', 'g': 'e', 'h': 'f', 'i': 'q', 'j': 'o', 'k': 'h', 'l': 'g', 'm': 'm', 'n': 'v', 'o': 'i', 'p': 'u', 'q': 'd', 'r': 'l', 's': 'y', 't': 'k', 'u': 'n', 'v': 'b', 'w': 'w', 'x': 't', 'y': 'c', 'z': ' ', ' ': 'j'}\n", "Inv table: {' ': 26, 'a': 6, 'b': 21, 'c': 23, 'd': 16, 'e': 6, 'f': 6, 'g': 9, 'h': 8, 'i': 10, 'j': 0, 'k': 12, 'l': 10, 'm': 7, 'n': 10, 'o': 6, 'p': 0, 'q': 4, 'r': 0, 's': 1, 't': 6, 'u': 3, 'v': 2, 'w': 3, 'x': 1, 'y': 1, 'z': 0}\n", "Sixth Test Succeeds\n" ] } ], "source": [ "p = P().shuffle()\n", "inv = p.inversion_table()\n", "print(\"Perm:\", p._code)\n", "print(\"Inv table:\", inv)\n", "new_p = P(inv_table = inv)\n", "try: \n", " assert p == new_p\n", " print(\"Sixth Test Succeeds\")\n", "except AssertionError:\n", " print(\"Sixth Test Fails\") " ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Finally, we should talk about the order and the parity of a permutation. \n", "\n", "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.\n", "\n", "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." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "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." ] }, { "cell_type": "code", "execution_count": 17, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Perm: {'a': ' ', 'b': 'w', 'c': 'h', 'd': 'n', 'e': 'l', 'f': 't', 'g': 'i', 'h': 'a', 'i': 'o', 'j': 'g', 'k': 'p', 'l': 'x', 'm': 'r', 'n': 'c', 'o': 'v', 'p': 'q', 'q': 'b', 'r': 'm', 's': 'f', 't': 'u', 'u': 'y', 'v': 'e', 'w': 'k', 'x': 'd', 'y': 'j', 'z': 's', ' ': 'z'}\n", "Order: 20\n", "Sign: 1\n", "Seventh Test Succeeds\n" ] } ], "source": [ "p = P().shuffle()\n", "order = len(p)\n", "sign = p.sgn()\n", "print(\"Perm:\", p._code)\n", "print(\"Order:\", order)\n", "print(\"Sign:\", sign)\n", "try: \n", " inv_p = ~p\n", " assert p.sgn() == inv_p.sgn()\n", " assert P().sgn() == 1 # identity is even\n", " print(\"Seventh Test Succeeds\")\n", "except AssertionError:\n", " print(\"Seventh Test Fails\") " ] } ], "metadata": { "kernelspec": { "display_name": "Python 3", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.7.7" } }, "nbformat": 4, "nbformat_minor": 4 }