Permutation Library 1.0
(C) E. D. Rivlis

1. Introduction

  This library deals with permutations. As far as I know this library is unique.

  To understand permutations one can see them as simple functions of integers.
Let A be the permutation so that A(1)=2 A(2)=5 A(3)=4 A(4)=1 A(5)=3 and for i>5 A(i)=i.
Another notation is:

/   1    2    3    4    5    6    7    8    9  ... \ = / 1 2 3 4 5 6 7 8 9 ... \ 
\ A(1) A(2) A(3) A(4) A(5) A(6) A(7) A(8) A(9) ... / = \ 2 5 4 1 3 6 7 8 9 ... /

  One can easily see that indices for 6 7 8 9 etc. are not really needed to represent the
permutation.It's obvious that for any finite permutation exists a interger j  such as that for
all j<i A(i)=i. It is customery only to reffer to all the i such as 1<i<j. So we are left with:
/ 1 2 3 4 5 \
\ 2 5 4 1 3 /
But we don't really need the upper indices / 1 2 3 4 5 \ too, because they are just the ordered
integer between 1 and i-1. And at last we are left with  \ 2 5 4 1 3 / or {2 5 4 1 3}.

Another way to represent a permutations is a cycle.
I'll write the following statement:
1 -> A(1) = 2 -> A(2) = 5 -> A(5) = 3 -> A(3) = 4 -> A(4) = 1
We got a cycle! 
We can write it in a more compact fashion as {{1 2 5 3 4}}

Let's look at another permutation B={2 1 3 5 4}. 
Remember that means that B(1)=2 B(2)=1 B(3)=3 B(4)=5 B(5)=4
The cycle will be then
1 -> B(1) =  2 -> B(2) = 1
What now? lets continue.
3 -> B(3) = 3
and
4 -> B(4) = 5 -> B(5) = 4
We got three different cycles!
The total cycle is then {{1 2}{3}{4 5}}
(now you understand why on uses {{ }} ).

  What will happen now if we'll make a composite function from A and B?
let's see:
C(1)=B(A(1))=B(2)=1
C(2)=B(A(2))=B(5)=4
C(3)=B(A(3))=B(4)=5
C(4)=B(A(4))=B(1)=2
C(5)=B(A(5))=B(3)=3
it's really simple then, BA=C={1 4 5 2 3}
and the cycle is {{1}{2 4}{3 5}}

  What if we use B and then A?
well...
D(1)=A(B(1))=A(2)=5
D(2)=A(B(2))=A(1)=2
D(3)=A(B(3))=A(3)=4
D(4)=A(B(4))=A(5)=3
D(5)=A(B(5))=A(4)=1
so AB=D={5 2 4 3 1},
and the cycle is {{1 5}{2}{3 4}}

this result shows that AB dosn't have to be equal to BA.

  We'll define now a new permutation M in the following way:
A(M(i))=i
1=A(4) -> M(1)=4
2=A(1) -> M(2)=1
3=A(5) -> M(3)=5
4=A(3) -> M(4)=3
5=A(2) -> M(5)=2
so M={4 1 5 3 2}while the cycle is {{1 4 3 5 2}}
M is called the inverse permutation to A
from the definition it's easy to see that AM=MA={1 2 3 4 5}
which is the identity permutation.

2. The Functions

(/Gs) (/Gt) symbolize the Greek letters Sigma and Tau reespectivly. They are commonly used as
symbols of permutations. The library contains the following operators:
 
(/Gs)IDN	
Identity permutation command:
Returns an identity permutation; that is, a list of ordered integers.

Input 		n
Output 		{1 2 3...n}

Example	1: 3  -->  1: {1 2 3}


(/Gs)RND
Random permutation command:
Returns a random permutation; that is, a list of unordered integers.

Input		n
Output 		{I1 I2 I3 ...In}

Example	1: 5  -->  1: {5 4 1 3 2}

(/Gs)x(/Gt)	
Permutation composition operator:
Returns the composition of the arguments.
 
Input		{I1 I2 I3 ...In}
		{J1 J2 J3 ...Jm}
Output		{K1 K2 K3 ...Kp}  p=max(m,n)

Example	2: {5 4 1 3 2}	1: {2 3 1}  	-->	1: {5 4 2 1 3}
	2: {2 3 1}	1: {5 4 1 3 2}	-->	1: {4 1 5 3 2}

(/Gs)INV
Inverse permutation function:
Return the inverse permutation.
 
Input		{I1 I2 I3 ...In}
Output		{J1 J2 J3 ...Jn}

Example	1: {4 1 5 3 2}	-->	1: {2 5 4 1 3}


(/Gs)SIGN
Permutation sign command:
Returns the sign of the permutations; that is, 1 for even permutations and -1 for odd
permutations.
 
Input		{I1 I2 I3 ...In}
Output		1 or -1

Example	1: {2 5 4 1 3}  -->  1: 1
	1: {2 1 3}  	--> 1: -1

(/Gs)->CY
Permutations to Cycle command:
Returns the cycle, which is equivalent to the permutations.
 
Input		{I1 I2 I3 ...In}
Output		{{J1..Ja}{K1..Kb}...{L1..Lc}}

Example	1: {2 5 4 1 3}	-->	1: {{1 2 5 3 4}}
	1: {1 2 3 4 5}	-->	1: {{1}{2}{3}{4}{5}}
	1: {2 1 3 5 4}	-->	1: {{1 2}{3}{4 5}}

CY->(/Gs)
Cycle to Permutation command:
Returns the permutation, which is equivalent to the cycle.
 
Input		{{I1..Ia}{J1..Jb}...{K1..Kc}}
Output		{L1 L2 L3 ...Ln}

Example	1: {{1 4 6}{2 5}{3}}	-->	1: {4 5 3 6 2 1}
	1: {{6 1 4}{3}{5 2}}	-->	1: {4 5 3 6 2 1}



This library is based on UserRPL Programs I wrote. So it's not that efficient.
I'm planning on importing them into SysRPL or even ML in the future.
Eran Rivlis 

(EMAIL: dartin@www-mail.huji.ac.il) 
