Counting and generating Permutations

You may have seen puzzles where you have to arrange tiles in different orders.

Consider 4 letters a,b,c,d. How many ways can they be arranged in order ? We have

abcd

abdc

acbd

acdb

adbc

adcb

bacd

badc

…

and so on. If you listed them all you could see that there are 24 rows in all. There are exactly 24 ways of arranging 4 letters in order. In this short lesson we will examine the process of placing different objects in order and see how it works. Then we will look at some Python code that illustrates this

Imagine you have a bag of four tiles a,b,c,d. You have a row of 4 spaces to put the tiles in, like, say, a mini scrabble board. You stick your hand in the bag and remove a tile, placing it in position one. well at this stage there are 4 different tiles it could be, so we can see that there are 4 families of orderings, one starting with a, one with b, and so for c and d. so let’s write down

4

now you want a tile for position 2. well now you only have 3 choices of tile left. so there are 3 subfamilies for each ordering that starts with whatever tile tile 1 was. so we now have

4 x 3

now there are only two tiles left so we write

4 x 3 x 2

and finally there is only one tile left. No choice at all – we are compelled to use whatever is the last tile, so we write

4 x 3 x 2 x 1

now what is the result of this multiplication ? well you can probably guess, it is 24, which is what we started with … the number of ways of arranging 4 tiles in order. OK, but now we have learned something powerful, because a little application of our logical method from above can clearly show that if you have 5 tiles then there must be

5 x 4 x 3 x 2 x 1 ways of arranging them

what’s this ? well we can use a shortcut to see that it must be 5 x 24 = 120

I hope you can now see a pattern emerging… for n tiles the total number of arrangements must be

n x (n-1) x (n-2) x (n-3) x … 2 x 1

there is a name for the numbers you get using this formula. they are called the factorials and are usually denoted by n! (yes an exclamation mark… strange but useful). Here is code

def fac(x):
    if x==0:
        return 1
    else:
        return x*fac(x-1)
 
for a in range(10):
    print a

here are the first few

n	n!
1	1
2	2
3	6
4	24
5	120
6	720
7	5040
8	40320
9	3628800

You can see they grow fast as n increases. this means that situations when you have a lot of starting choices quickly become very complex with a lot of possibilities. They call it a combinatorial explosion. Consider the case of having 100 different tiles to arrange. the total number of ways would be 100! which is

9332621544394415268169923885626670049071596826438162

1468592963895217599993229915608941463976156518286253

697920827223758251185210916864000000000000000000000000

This means that if you arranged one tile a second it would take more than the lifetime of the universe to lay them all out. Don’t try it at home kids.

Here is some code to generate every permutation of a string of symbols. It uses a generator function.

def perm(a):
if len(a)==1:
        yield a
    else:
        for i in range(len(a)):
            this = a[i]
            rest = a[:i] + a[i+1:]
            for p in perm(rest):
                yield this + p
for x in perm(‘abcde’):
    print x

This is a recursive function, that calls itself. It can be tricky to get the hang of these at first.

As with many things we have to try and make the knowledge our own, run through it until you see the inner logic. That grasp of methods and logics will expand as your number sense expands, showing you interesting and powerful glimpses of hidden structure in the multiverse. It will also allow you to build your house on the rock of reliable reasoning which may improve you confidence and skills in other areas. See it as like going for a good walk, one might ask, as some people do of maths “what’s the point ?” – the point of a walk is that it’s fun and it makes you fit. As you build your maths knowledge the “point” of doing it will unfold before you like a wonderful peacock’s tail. Maybe you will even catch a glimpse of the Mind of God.