Euler
Examplesby 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.
>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)
()
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
>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
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
>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]
What integer solutions exist for the following equations.
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
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