multiplying permutations

classic Classic list List threaded Threaded
3 messages Options
Reply | Threaded
Open this post in threaded view
|

multiplying permutations

Kirby Urner-6
"""
Source code for math-teach post
by Kirby Urner / OST
(c) GNU Public License, 2011
"""

import string, random

charset = list(string.ascii_lowercase + " ")

def make_perm( ):
    "make some random permutation object mapping " ",a-z into itself"

    target = charset[:] # copy all
    random.shuffle(target)  # in place reordering
    return Pobject(dict( zip(charset, target)))

class Pobject:
    """
    permutation objects are instantiated with a dict.  they
    may be multiplied and/or inverted
    """

    def __init__(self, perm):
        self.perm = perm

    def encrypt(self, plaintext):
        e = ''
        for char in plaintext:
            e += self.perm[char]
        return e

    def decrypt(self, ciphertext):
        e = ''
        inv = ~self # invert the permutation
        return inv.encrypt(ciphertext)

    def __invert__(self):
        invdict = {}
        for char in self.perm:
            invdict[self.perm[char]] = char
        return Pobject(invdict)

    def __mul__(self, other):
        output = {}
        for char in self.perm:
            output[char] = other.perm[self.perm[char]]
        return Pobject(output)

    def __repr__(self, abbrev = False):
        return str(sorted(self.perm.items(), key=lambda t: t[0]))
_______________________________________________
Edu-sig mailing list
[hidden email]
http://mail.python.org/mailman/listinfo/edu-sig
Reply | Threaded
Open this post in threaded view
|

Re: multiplying permutations

kirby urner-4
Here's some verbiage on math-teach giving some context for the
just-posted source code:

http://mathforum.org/kb/message.jspa?messageID=7403815&tstart=0

There's a perennial thread on some math teaching groups as to whether
multiplication should be conveyed as "repeated addition", which often
seems the sensible approach, but always?

In going to other meanings of multiplication, with a family
resemblance to rational number multiplication (e.g. existence of
inverse such that p * ~p = 1), we venture more into abstract algebra
territory.

This is where Python shines, as one of those language making operator
overloading a snap.  Write a class, define __mul__ to suit.

Kirby

On Thu, Mar 10, 2011 at 3:43 PM, Kirby Urner <[hidden email]> wrote:
> """
> Source code for math-teach post
> by Kirby Urner / OST
> (c) GNU Public License, 2011
> """
_______________________________________________
Edu-sig mailing list
[hidden email]
http://mail.python.org/mailman/listinfo/edu-sig
Reply | Threaded
Open this post in threaded view
|

Re: multiplying permutations

Andrzej Kapanowski
Hello!
Here is a useful class to handle permutations.
-----------------------------------------------------------------
class Perm:
    def __init__(self, size, cycle=None):
        self.size = size
        self.data = range(size)
        if cycle:
            n = len(cycle)
            for i in range(n):
                self.data[cycle[i]] = cycle[(i+1) % n]
    def __str__(self):
        return str(self.data)
    def __mul__(self, other):
        if self.size != other.size:
            print "error: different size"
            return
        tmp = Perm(self.size)
        for key in range(tmp.size):
            tmp.data[key] = self.data[other.data[key]]
        return tmp
    def __invert__(self):   #  ~p
        tmp = Perm(self.size)
        for i in range(tmp.size):
            tmp.data[self.data[i]] = i
        return tmp
-------------------------------------------------------------------------------------
# Exemplary calculations
N = 4

E = Perm(N)
R1 = Perm(N,(0,1)) * Perm(N,(2,3))
R2 = Perm(N,(0,2)) * Perm(N,(1,3))
R3 = R1 * R2
# {E, R1, R2, R3} form D_2 group

H = Perm(N,(0,1,3,2))
print H, ~H, H*(~H)
-------------------------------------------------------------------------
Regards,
Andrzej Kapanowski


_______________________________________________
Edu-sig mailing list
[hidden email]
http://mail.python.org/mailman/listinfo/edu-sig