Chief Wahoo

Fun with permutations

:snake:


A permutation is a bijective mapping of a set to itself. For example, if we had the set defined as , just the natural numbers from one to ten, then the permutation mapping to itself (written ) could be represented as follows:

The numbers on top line are the elements of and the numbers on the bottom line are the permuted values. For example, the above shows that

It’s not a tremendously exciting permutation, most of the numbers just map back to themselves, for example and so on. Consider a second permutation of , called :

Every number maps to something different, with the exception of 10, which doesn’t change. Moving swiftly on, consider what happens if we compose the permutation with the permutation , which is written . That means we get the value from and apply it to , like this:

Let’s try it with an actual value from , how about 6:

Interesting, 6 doesn’t map to 5 under either permutation, so looks like a new permutation entirely. If we run all the values of through our new permutation, we can write the whole thing out as follows:

Not so different. Quite some of seems preserved; 7 maps to 8 in the same way. Let’s apply our first permutation to itself (we write this for brevity) and see what happens. Remembering that first permutation:

Let’s pick one of the numbers that is actually changed under the mapping and run it through twice.

What happens if we keep going?

Ah ha! The cycle is complete; we started at 2 and got back there. It’s easy to see if we keep raising to higher powers we will repeat ourselves every third power. Let’s think about our permutations slightly differently. We can show the cycle we have observed more clearly if we use a different notation for our permutation:

That just means 2 maps to 7 maps to 5 and then back to 2. Anything not mentioned just maps to itself (nothing interesting happens). With the above notation, we can clearly see that the orbit has a length of three. It’s interesting that we got 2 to map back to itself at the third power. Let’s write out in the same way:

It has a longer orbit of length nine, so (following from what we discovered above) let’s see what happens when we raise it to the ninth power. This is going to get ugly!

This will work for any and we have it that the ninth power of is the identity of the permutation (so ), which we generally just write for brevity. This is what we mean:

We also say that has an order of nine, that is that we will find the identity at the ninth power of . In the case that a permutation only has one orbit, the order of that permutation is simply the cardinality (length) of its (single) orbit.

What happens if we have a permutation with more than one orbit? Let’s introduce another permutation that has two orbits:

Exciting! But let’s write that out in our “cycle” notation, to be clear:

The order of a permutation with more than one orbit will be the lowest common multiple of the cardinalities of its orbits (which are 2 and 4). Since 2 is a multiple of 4, the order of is 4. In other words; after four iterations the 4-cardinality orbit has completed one cycle, and the 2-cardinality orbit has completed two cycles all orbits are in a state or completion.

What happens to the order of a permutation when it is composed?

Let’s return to our first two permutations:

Let’s write out their composition again, as above:

But let’s also write the orbits out in cycle notation:

We can see that the permutation has three orbits with cardinalities 4, 3 and 2. The lowest common multiple of these numbers is 12, so we have that and that the order of is 12.

But what if we wanted to compose with and and to find out what the order of ? We would have to track each number through three permutations ... what a drag! Let’s just write some code to do it for us. We can also test our hypotheses about the relationship between orbit cardinality and order.

The first thing to define would be a permutation. I want to write a Python class that I can instatiate with some orbits and then call with numbers, just like we do in the notation above. Perhaps something like:

α = (1, 7, 8, 9)(2, 3, 4)(5, 6)

Unfortunately, the above would interfere with the calling syntax of Python and require me to override the tuple builtin (which I’m not even sure is possible). Besides which, we can’t use non-ASCII characters in identifiers in Python. Instead I would be happy to settle for something like:

class Permutation(object):

    def __init__(self, name, orbits):
        pass

a = Permutation('α', (
    (1, 7, 8, 9), (2, 3, 4), (5, 6)
))

Hurrah! We’ve defined half of a permutation in Python. Pity it doesn’t actually do anything. What do permutations do? Well in terms of our definition above, they just return the “next” thing for one of their orbits.

The code for cycling through an orbit (the handful of tuples passed to our Permutation constructor above) should be pretty straightforward. We just need to return the “next” number, looping if we reach the end of the tuple:

def follow_orbit(orbit, num):
    'Follow an orbit one step from the passed number'
    index = orbit.index(num) + 1
    if len(orbit) == index:
        return orbit[0]
    return orbit[index]

I’d then like to be able call my permutation in the same way I show application happening in my notation. Thusly;

>>> a(2)
7

To do this, we can define the “dunder” method __call__ on our class, which will be the method that is called when the class instance is called (a above is a class instance). Our __call__ method here would just use the follow_orbit function to return the appropriate number. Let’s put it all together:

class Permutation(object):

    def __init__(self, name, orbits):
        self.name = name
        self.orbits = orbits

    def __call__(self, num):
        for orbit in self.orbits:
            if num in orbit:
                return follow_orbit(orbit, num)
        return num  # not changed in the permutation

a = Permutation('α', (
    (2, 7, 5),
))

a(2) == 7  # True

To calculate using our Python code above, we would have to write:

a(a(2)) == 5  # True

This isn’t particularly useful if we need to raise our permutation to the 100th power. Suppose we wanted to write using our Python class, we would have to write:

a(b(a(b(a(b(a(b(2)))))))) ===  # ???

The first thing to realise is that in this situation, “raising to a power” is equivalent to composing a permutation with itself, I claim and . So we have it that “raising to a power” is just a special case of composition.

That said, until we come up with a way of representing composition in our code, our Permutation class is pretty useless. Python being Python, there’s exactly what we need in the standard lib in the form of functools.reduce. Before we can enjoy the stdlib goodness, and we need to define a function that composes just two functions, which is pretty simple:

def compose_left_right(left, right):
    return lambda x: left(right(x))

The above function just takes a pair and returns a closure that will call left with the return value of right. Let’s put it into action with a simple composition:

def add_two(num):
    return num + 2

def multiply_two(num):
    return num * 2

multiply_then_add = compose_left_right(add_two, multiply_two)

multiply_then_add(2) == 6  # True

We can see that the multiplication happened first, we would have got 8 if the addition happened first. The above can be generalised from two functions (left and right), to n functions by using functools.reduce and a little * magic:

def compose(*functions):
    return functools.reduce(compose_left_right, functions)

Now to define our special case of composition “raising to a power”, which is just composing a function with itself a given number of times:

def power(fn, to):
    return compose(*[fn] * to)

Wait, we’re not done yet! We need one more function to test whether or not some permutation (or a composition of permutations raised to a power) is the identity of a set. Let’s dip into the standard lib once more and fish out itertools.starmap and operator.eq:

def identity(of, permutation):
    result = zip(of, map(permutation, of))
    return all(itertools.starmap(operator.eq, result))

The variable result above will be a list of 2-tups just like our very first representation of a permutation. Once we have that, all that remains to be done is make a pairwise comparison per tuple (that’s where itertools.starmap and operator.eq come in); if all the pairwise comparisons come back True, then we have our identity.

Making use of the Python code we’ve written, we can find the order of the composition of the permutations we have defined above without having to do much more than describe the permutation in Python’s terms:

S = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}

a = Permutation('α', (
    (2, 7, 5),
))

b = Permutation('β', (
    (1, 2, 3, 4, 5, 6, 7, 8, 9),
))

c = Permutation('γ', (
    (1, 7), (3, 6, 10, 9),
))

abc = compose(a, b, c)

to = 1

while not identity(S, power(abc, to)):
    to += 1

print("Order is {0}!".format(to))

Running the above code is left as an exercise to the reader, it’s also available on GitHub.