Permutation Library 1.0

E. D. Rivlis © 1997-1998

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 : {I1 I2 I3 ...In}
    example :  
    1: 5  --> 1: {5 4 1 3 2} 

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

    input : {I1 I2 I3 ...In}
    {J1 J2 J3 ...Jm}
    output : {K1 K2 K3 ...Kp} 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 : {I1 I2 I3 ...In}
    output : {J1 J2 J3 ...Jn}
    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 : {I1 I2 I3 ...In}
    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 : {I1 I2 I3 ...In}
    output : {{J1..Jp}{K1..Kq}...{L1..Lr}}
    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 : {{I1..Ip}{J1..Jq}...{K1..Kr}}
    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

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