Permutation Library 1.0

Download the library.

1. Introduction

1.1 What are permutations?

This library deals with permutations. As far as I know it 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}.

* * *

1.2 Cycles

Another way to represent a permutations is a cycle. Look at 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 it means that
B(1) = 2 B(2) = 1 B(3) = 3 B(4) = 5 B(5) = 4. The cycle will then be:

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 one uses {{ }} ).

* * *

1.3 Composite permuation

What will happen 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}}. But what happens 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.

* * *

1.4 Inverse permutation

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 of 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

The Greek letters (Sigma) and (Tau), are commonly used as symbols of permutations. The library contains the following operators:

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}
RND
Random permutation command:
Returns a random permutation; that is, a list of unordered integers.

input : n

output : {I₁ I₂ I₃ ...I_n}

example :

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

x
Permutation composition operator:
Returns the composition of the arguments.

input : {I₁ I₂ I₃ ...I_n}
{J₁ J₂ J₃ ...J_m}

output : {K₁ K₂ K₃ ...K_p} where 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}

INV
Inverse permutation function:
Return the inverse permutation.

input : {I₁ I₂ I₃ ...I_n}

output : {J₁ J₂ J₃ ...J_n}

example :

1: {4 1 5 3 2} --> 1: {2 5 4 1 3}
SIGN
Permutation sign command:
Returns the sign of the permutations; that is, 1 for even permutations and -1 for odd permutations.

input : {I₁ I₂ I₃ ...I_n}

output : 1 or -1

example :

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

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

->CY
Permutation to Cycle command:
Returns the cycle, which is equivalent to the permutation.

input : {I₁ I₂ I₃ ...I_n}

output : {{J₁..J_p}{K₁..K_q}...{L₁..L_r}}

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->
Cycle to Permutation command:
Returns the permutation, which is equivalent to the cycle.

input : {{I₁..I_p}{J₁..J_q}...{K₁..K_r}}

output : {L₁ L₂ L₃ ...L_n}

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

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