[Edu-sig] Permutations with Python

[kirby urner]

>
> import unittest
> from px_class import P
>
> class Test_Permutation(unittest.TestCase):
>
>     def test_1(self):
>         """
>         any p * ~p should give Identity
>         """
>         p = P() # identity permutation
>         new_p = p.shuffle()
>         inv_p = ~new_p
>         self.assertEqual(p, inv_p * new_p, "expected identity fails")
>
>


Of course where there's multiplication (__mul__) we might reasonably expect
not only __pow__, but also __truediv__.

These "__ribs__" come as a package with the API we call "Algebra" and based
on patterns, we'd expect:

    def __truediv__(self, other):
        return self * ~other

where unary ~ makes sense especially in a one-operation Group universe,
where each instance is guaranteed to have its unique pair.  __invert__ is a
part of our P class already:

    def __invert__(self):
        """
        create new P with reversed dict
        """
        newP = P(' ')
        newP._code = dict(zip(self._code.values(), self._code.keys()))
        return newP

A pair of inverses (p and ~p) when  "__mul__-tiplied" together, return the
Neutral or Identity P, returned by P().  Put another way, p / p == p * ~p
== P(), where p = any P().shuffle().

__mul__ and __truediv__ are examples of the same idea: binary operators
with a set of instance type things to work with as a group.

The permutation class provides an idealized algebraic "good citizen" in a
rather constrained finite world.

Adding another test then:

    def test_3(self):
        """
        lets have a division operation!  a / b == a * ~b
        or equivalently a / b == a * b**-1
        """
        p = P().shuffle() # arbitrary permutation
        q = P().shuffle() # arbitrary permutation
        r = p / q
        # if r = p / q then r * q = p
        self.assertEqual(p, r * q, "expected identity fails")
        r = q / p
        # if r = q / p then r * p = q
        self.assertEqual(q, r * p, "expected identity fails")


Note that from the LCM of the subcycles (their orders i.e. sizes) you get
the number of powerings for this permutation to do a full orbit, back to
its own beginning.  Each one has an orbit through this factorial-sized
space of possibilities.

By subcycles I refer to the cyclic output, a tuple of tuples, which my P
supports (in the J language it's one of the primitives):

In[118]: p = P().shuffle()  # scare up a random scramble of the alphabet

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

p.cyclic()
Out[120]:
(('x', 'n', 'h', 'p', 'y', 'a', 'k', ' ', 'u', 'e', 'f', 'z', 'i', 'b',
'd', 'c', 'j'),
 ('t', 'v', 'w'),
 ('s', 'm', 'l', 'g', 'r'),
 ('o', 'q'))

You see how to read these.  The dict pairs 'p' with 'y' and then 'y' with
'a', 'a' with 'k' whereas 'y', 'a', 'k' is all part of the first / longest
tuple, one of the cycles or subcycles (a subgroup).

The last element in a tuple connects back to the first, as what it maps to,
and then we're on to the next cycle, covering the same ground the dict
version covers, two ways of saying the same thing.

The LCM (lowest common multiple) of several numbers is computed from their
GCD (greatest common divisor) which we have seen many times -- both often
developed along with class Q, the Rational Number class (p, q both int, as
if fractions.Fraction did not exist yet).

We also need GCD for determining relatively prime numbers, ergo the
totatives of N.  These form more examples of Groups, when multiplied modulo
N.

Fermat's Little Theorem, then Euler's generalization thereof, branch off
from here (or converge to here, depending on if we're arriving at or
leaving the train station (hub)).

Like some others, I've made conquering RSA (the encryption algorithm) a
local peak in my curriculum as well (have for a long time).  Neal
Stephenson was influential.  Here's a web page of mine from around Y2K:

http://www.4dsolutions.net/ocn/clubhouse.html

Likewise we've been through this material before on edu-sig.

The search, the quest, is for sweet spots, "holy wells" (grails) that
contain a digestible portion of:

(A) reasonably meaty Python
(B) reasonably interesting mathematics

We seek these synergies in order to maximize practical mastery of at least
one computer language (swap in your current favorite) but also to suggest
continuity should more curricula pick this up.

A Permutation in Clojure might be the next step, with the same concept
reintroduced.  Then on to Java?  I'm sure this code is out there, many
times, but we lack much agreement at the curriculum level that this should
be a trunk road.

I'm using this framework currently with students mainly just to introduce
unit testing, the whole idea, in addition to operator overloading.
Tomorrow I plan on having the Permutation retch (as in barf) if a 2nd
argument is fed in that's not an iterable.

How might that look?  If we raise a TypeError in that case, how might we
reflect this expected outcome in the form of a unit test?

It's not just operators we overload in Python, but object-calling syntax
(__call__) along with getting / setting syntax (__getitem__), as well as
attributes (__getattr__, __setattr__).  The Permutation provides a natural
step-ladder up through at least some of those freedoms / capabilities.  We
keep spiraling back for more.

I'm also taking advantage of encrypt and decrypt functions to talk about
file I/O.  We read in declaration.txt (a mix of upper and lowercase, as
well as punctuation -- so permute accordingly) and store it out as
"encrypted" -- along with a JSON string, the "key".

With access to such a key, comes easy transformation back to the starting
text, a good metaphor for encoding when not encrypting exactly (there's a
fine line).

I'm always clear these are super easy to break "codes" and it's more a
matter of breaking into topical content, wrapping one's mind around some
linchpin concepts in both programming and mathematics, that we get our
payoff.

The group stuff is a great jumping off point towards vectors, vector
spaces, and polyhedrons spinning.  That's another rich area for meaty code
around generic concepts, lots of payoff.

In the namespace of my Digital Mathematics, I'm working on a tunnel from
Casino to Martian Math.  I know its abstruse but I break it down into
Neolithic -> Martian Math for a timeline and Casino <--> Supermarket for
two "wings" having to do with mathematics in the real world.

http://wikieducator.org/Digital_Math

Permutations connect us to combinatorics on the one hand, and to rotating
polyhedrons on the other.  That's the kind of Lexical <-> Graphical bridge
I look for, regardless of my level of belief in a left and right brain and
all the additional polarities that might line up under left and right
respectively.  Getting visualizations and symbolic reasoning to work
together is nevertheless a goal.

Youtubes in the same territory:

https://youtu.be/VSB8jisn9xI

https://youtu.be/q1riFCCsUU4
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/edu-sig/attachments/20151123/53427a79/attachment.html>