iconEuler Examples

Permutations

by R. Grothmann

The functions for permutations store permutations as bijective mappings of 1:n to itself. There are, however, functions to enter and print permutations as cycles.

For the documentation see the following link.

Permutations

>load perm.e
Functions for permutations.

The functions all start with "p". The identity is pid. To print the cycles of a permutation, use pprint. The identity does not cycle anything.

>pprint pid(5)
()

Here is the full internal form of a permutations. The meaning is: 1 is mapped to 1, 2 to 2 etc.

>pid(5)
[1,  2,  3,  4,  5]

Transposition of 2 and 3 in 1:5. Note that pprint can be used in prefix form.

>pprint ptranspose(2,3,5)
(2 3)

Once again the internal form.

>ptranspose(2,3,5)
[1,  3,  2,  4,  5]

We can set the default n for ptranspose and pcycle.

>pn=10;

Multiplication of permutations with the operator pm.

>pprint ptranspose(2,3) pm ptranspose(3,4)
(2 3 4)

An alternative is pmult. Note that multiplication of permutations does not commute.

>pprint pmult(ptranspose(3,4),ptranspose(2,3))
(2 4 3)
>pprint ptranspose(2,3) pm ptranspose(7,8)
(2 3)(7 8)

Enter cyclic permutations.

>pprint pcycle([1,2,3],10)
(1 2 3)

Another cyle (with default n=10).

>pprint pcycle([1,10,8])
(1 10 8)

List form of this permutation.

>pcycle([1,10,8])
[10,  2,  3,  4,  5,  6,  7,  1,  9,  8]

Here is the meaning of this written as a mapping.

>format(4,0); (1:10)_pcycle([1,10,8]), longformat;
  1   2   3   4   5   6   7   8   9  10 
 10   2   3   4   5   6   7   1   9   8 

Inverse permutation.

>h=pcycle([1,2,3,4]);
>pprint pinverse(h)
(1 4 3 2)

Test inverse. () is the identical permutation, written in cyclic form.

>pprint h pm pinverse(h)
()

Multiplication is associative, however, meaning that brackets do not matter. So we can just use no brackets.

>pprint h pm h pm pinverse(h) pm pinverse(h)
()

Iterate through Permutations

Now we show how to loop over all permutations.

>function doprint(p) ...
 pprint(p), 
 endfunction

The function forAllPerm runs another function for all permutations.

>forAllPerm("doprint",3);
()
(2 3)
(1 2)
(1 2 3)
(1 3)
(1 3 2)

We can also loop over all round trips. These are cycles involving all elements.

>forAllTrips("doprint",4);
(1 4 3 2)
(1 3 2 4)
(1 3 4 2)
(1 4 2 3)
(1 2 4 3)
(1 2 3 4)

For other purposes, there is a function forAllChoices, which runs a function through all unordered choices of m elements out of 1:n.

Let us count the coices.

>function docount (p) ...
   global s;
   s=s+1;
 endfunction
>s=0; forAllChoices("docount",10,4); s,
5040

Since we have n choices for the first element, n-1 for the next etc. we get for the number of unordered tupels of m element out of n

Permutations

>10!/6!
5040

Another function runs f through all ordered tupels. Let us test it by printing all tupels.

>function giveout (p) ...
 p,
 endfunction
>forAllOrderedChoices("giveout",6,3);
[1,  2,  3]
[1,  2,  4]
[1,  2,  5]
[1,  2,  6]
[1,  3,  4]
[1,  3,  5]
[1,  3,  6]
[1,  4,  5]
[1,  4,  6]
[1,  5,  6]
[2,  3,  4]
[2,  3,  5]
[2,  3,  6]
[2,  4,  5]
[2,  4,  6]
[2,  5,  6]
[3,  4,  5]
[3,  4,  6]
[3,  5,  6]
[4,  5,  6]

The number is bin(n,m), of course.

>bin(6,3)
20

Stationary Points

There is a recursive way to compute the number of all permutations that keep no point at its place.

We add up the number of permutations, which leave exactly k points of N at its place for k=1 to N-1, and add 1. This is the number of permutations, which keep at least one point at its place. N! minus this number is the desired number.

We use Euler's matrix language to compute this. The vector v contains the result for n=1,..,N.

>function allpert (n) ...
 v=[0];
 loop 2 to n
   v=v|(#!-(1+sum(bin(#,(#-1):-1:1)*v)));
 end
 return v;
 endfunction

Here are the results for N=1 to 5.

>allpert(5)
[0,  1,  2,  9,  44]

We want to check this. So we iterate over all permuations and add 1 to a global variable s, if all numbers changed their places.

>function f(p) ...
 global s;
 if all(p<>1:cols(p)) then s=s+1; endif;
 return p;
 endfunction

The result is correct.

>s=0; forAllPerm("f",5); s,
44

It is a famous fact, that the probability of all numbers to change place converges to a limit for n to infinity.

>allpert(20)/fac(1:20)
[0,  0.5,  0.333333333333,  0.375,  0.366666666667,  0.368055555556,
0.367857142857,  0.367881944444,  0.367879188713,  0.367879464286,
0.367879439234,  0.367879441321,  0.367879441161,  0.367879441172,
0.367879441171,  0.367879441171,  0.367879441171,  0.367879441171,
0.367879441171,  0.367879441171]

The limit is 1/e, which can be proved using

Permutations

>1/E
0.367879441171

Let us check the formula above.

>k=0:10; cumsum((-1)^k/k!)
[1,  0,  0.5,  0.333333333333,  0.375,  0.366666666667,
0.368055555556,  0.367857142857,  0.367881944444,  0.367879188713,
0.367879464286]
>allpert(10)/(1:10)!
[0,  0.5,  0.333333333333,  0.375,  0.366666666667,  0.368055555556,
0.367857142857,  0.367881944444,  0.367879188713,  0.367879464286]

Solving Integer Equations

What integer solutions exist for the following equations.

Permutations

with the side condition that a-i take the values 1-9 in a unique way.

>function check ([a,b,c,d,e,f,g,h,i]) ...
   if a-b==c and b*e==f and a+b==d and g-h==i/b then
     [a,b,c,d,e,f,g,h,i],
   endif;
 endfunction

f checks, if a,b,c,d,e,f,g,h,i (stored in a vector) satisfy the equations. Then we just have to loop over all permutations.

>forAllPerm("check",9)
[4,  3,  1,  7,  2,  6,  8,  5,  9]

So a=4, b=3 etc. is the unique solution.

Similar problems are

  SEND
 +MORE
 -----
 MONEY

Each letter can have only one meaning, of course.

Since obviously M=1, we need only choose 7 numbers of the numbers 0,2,3,4,5,6,7,8,9.

>v=[0,2,3,4,5,6,7,8,9]; 

The check function now is a bit more involved. For a selection p of 7 numbers from 1 to 9, we select the corresponding elements of our vector v, and store them in u. Then we can check, if this solutions is correct.

>function check (p) ...
 global v;
 u=v[p];
 a=u[1]*1000+u[2]*100+u[3]*10+u[4]; // send
 b=1000+u[5]*100+u[6]*10+u[2]; // more
 c=10000+u[5]*1000+u[3]*100+u[2]*10+u[7]; // money
 if a+b==c then
   a+"+"+b+"="+c,
 endif;
 endfunction

The function forAllChoices runs "check" through all choices of 7 elements from the numbers 1 to 9.

>forAllChoices("check",9,7)
9567+1085=10652

So the unique solutions is

  9567
 +1085
 -----
 10652

Python

This problem can be solved much faster in a language like C or Python. For this example, you have to install Python 2.7 (32-bit), of course.

We can use almost the same code.

>py: v=[0,2,3,4,5,6,7,8,9]

In the function, we need to take care that Python indices start with 0. Because we don't want to change the code, we add one additional element at the start of u.

>function python pycheck (p) ...
 global v
 u=[0]
 u.extend([v[i] for i in p])
 a=u[1]*1000+u[2]*100+u[3]*10+u[4]
 b=1000+u[5]*100+u[6]*10+u[2]
 c=10000+u[5]*1000+u[3]*100+u[2]*10+u[7]
 if a+b==c:
   print a, "+", b, "=", c
 endfunction

Python has a library "itertools", which can generate iterators over permutations.

>py: import itertools

It works much faster.

>py:  ...
 for p in itertools.permutations(range(9),7): ...
   pycheck(p)
9567 + 1085 = 10652

Examples