numericalMethods.algebra.group
Class Permutation

java.lang.Object
  |
  +--numericalMethods.algebra.group.Permutation

public class Permutation
extends java.lang.Object

Permutation.java

This class implements some static algorithms that deal with the group of permutations of finite sets. The permutation that sends {A,B,C,D} to {D,B,A,C} is encoded as {3,1,0,2} and its inverse {2,1,3,0} is the function from index to index.

Functions which are sensible to that notation have the Fun form which adopt the functional notation, for example times(int[], int[]) and timesFun(int[], int[]).

Methods which require an intermediate array (whether int[] or boolean[] of the same (or greater) length as the permutation) are provided with a signature that allows an instance to be passed on so that no intermediate instances are created. It is not thread safe and the values in these arrays are destroyed! In particular don't use twice the permutation array as the pair of parameters.

Created: Thu Nov 21 14:42:03 2002


Constructor Summary
Permutation()
           
 
Method Summary
static int applyTo(int[] s, int i)
          Returns j such that s[j]==i.
static int applyToFun(int[] s, int i)
          Returns s[i].
static int[][] cycles(int[] s)
          Returns the cycles of a given permutation, as int arrays.
static int[][] cyclesFun(int[] s)
          Returns the cycles of a given permutation understood as a function of the indices, as int arrays.
static java.lang.String cyclesToString(int[] s)
          Returns the cycles(int[]) view of the permutation as a String.
static java.lang.String cyclesToString(int[][] c)
          Returns the cycles(int[]) view of the permutation as a String.
static int[] divide(int[] p1, int[] p2)
           
static void divide(int[] p1, int[] p2, int[] result)
          Puts p1 composed with inverse(int[])(p2) into the third argument.
static int[] divideFun(int[] p1, int[] p2)
           
static void divideFun(int[] p1, int[] p2, int[] result)
          Puts p1[p2^-1[i]] into the third argument.
static int factorial(int n)
          factorial(n)=n!=n*(n-1)*...*1.
static void firstDerangement(int[] p)
          Let the parameter be the firstDerangement (permutation without fixed point) in the lexicographic order.
static void flipLR(int[] s)
          Flips the permutation left-right.
static void flipUD(int[] s)
          Flips the permutation up-down.
static int[] fromCycles(int[][] c)
          Returns a permutation built from its cycles.
static void fromCycles(int[][] c, int[] result)
          Changes result to a permutation of the same length, built from the given cycles.
static void fromCyclesFun(int[][] c, int[] result)
          Changes result to a permutation of the same length, built from the given cycles, as a function of the indices.
static int[] fromInversions(int[] inv)
          Returns the permutation having inv as its inversions vector.
static void fromInversions(int[] inv, int[] s)
          Returns the permutation having inv as its inversions vector.
static int[] fromInversionsFun(int[] inv)
          Returns the permutation, in functional notation, having inv as its inversions vector.
static void fromInversionsFun(int[] inv, int[] s)
          Returns the permutation, in functional notation, having inv as its inversions vector.
static int[] fromYoungTableaux(int[][][] y)
          Gives the pair of int[][] Young tableaux associated with the int[] permutation.
static int gcd(int[] nums)
          Computes the greatest common divisor of several numbers.
static int gcd(int m, int n)
          Computes the greatest common divisor of two numbers.
static int[] identity(int len)
          Returns an identity permutation of the desired length.
static void identity(int[] s)
          Replaces the int[] parameter with the identity of the same length.
static int[] inverse(int[] s)
          Returns the inverse permutation.
static void inverse(int[] s, int[] result)
          Changes result to the inverse permutation of s.
static int[] inversions(int[] s)
          Gives the inversion vector, that is, for each index, the number of greater indices to its left in the permutation.
static void inversions(int[] s, int[] result)
          Gives the inversion vector, that is, for each index, the number of greater indices to its left in the permutation.
static int[] inversionsFun(int[] s)
          Gives the inversion vector of a permutation in functional notation, that is, for each index, the number of greater indices to its left in the permutation.
static void inversionsFun(int[] s, int[] result)
          Gives the inversion vector of a permutation in functional notation, that is, for each index, the number of greater indices to its left in the permutation.
static boolean isDerangement(int[] p)
          Returns whether the given int[] is a valid derangement (permutation without fixed point) of the indices 0..length-1.
static boolean isDerangement(int[] p, boolean[] flags)
          Returns whether the given int[] is a valid derangement (permutation without fixed point) of the indices 0..length-1.
static boolean isDerangement(int[] p, int[] garbage)
          Returns whether the given int[] is a valid derangement (permutation without fixed point) of the indices 0..length-1.
static boolean isPermutation(int[] p)
          Returns whether the given int[] is a valid permutation of the indices 0..length-1.
static boolean isPermutation(int[] p, boolean[] flags)
          Returns whether the given int[] is a valid permutation of the indices 0..length-1.
static boolean isPermutation(int[] p, int[] garbage)
          Returns whether the given int[] is a valid permutation of the indices 0..length-1.
static int lcm(int[] nums)
          Computes the least common multiple of several numbers.
static int lcm(int m, int n)
          Computes the least common multiple of two numbers.
static void next(int[] p)
          Replaces a permutation with the next permutation in the cyclic lexicographic order.
static void nextDerangement(int[] p)
          Replaces a derangement (permutation with no fixed point) with the next derangement in the cyclic lexicographic order.
static int numInversions(int[] p)
          Each permutation can be written as a product of transpositions of consecutive elements.
static int numTranspos(int[] p)
          Each permutation can be written as a product of transpositions.
static int numTranspos(int[] p, boolean[] flags)
          Describe numTranspos method here.
static int numTranspos(int[] p, int[] garbage)
          Same as numTranspos(int[]) but uses a preinstanciated int[] of length at least the length of p.
static int order(int[] p)
          Returns the order of the given permutation.
static int order(int[] p, boolean[] flags)
          Describe order method here.
static int order(int[] p, int[] garbage)
          Same as order(int[]) but uses a preinstanciated int[] of length at least the length of p.
static int parity(int[] p)
          Gives the parity of the number of transpositions.
static void previous(int[] p)
          The previous one in the lexicographic order.
static int[] random(int len)
          Returns a random permutation on the letters 0..len-1.
static void random(int[] s)
          Replaces the parameter array with a random array on the letters 0..len-1 where len=s.length.
static void random(int[] s, int derangement)
          Replaces the parameter array with a random array on the letters 0..len-1 where len=s.length.
static int[] random(int len, int derangement)
          Returns a random permutation on the letters 0..len-1.
static int[][] runs(int[] s)
          Returns the runs of a given permutation, as int arrays.
static int[][] stringToCycles(java.lang.String s)
          Hands back an int[][] coded by a string.
static int[] stringToIntArray(java.lang.String s)
          Hands back an integer array coded by a string.
static int[] stringToIntArray(java.lang.String s, int[] basket)
          Hands back an integer array coded by a string.
static int subFactorial(int n)
          subFactorial(n+1)=!(n+1)=n*(!n+!(n-1))=[n!/E].
static int[] times(int[] p1, int[] p2)
           
static void times(int[] p1, int[] p2, int[] result)
          Composes two permutations.
static int[] timesFun(int[] p1, int[] p2)
           
static void timesFun(int[] p1, int[] p2, int[] result)
          Returns p1[p2[i]] in result.
static int[] timesInverse(int[] p1, int[] p2)
           
static void timesInverse(int[] p1, int[] p2, int[] result)
          Composes two permutations as functions and returns the permutation (contra-functional) notation in result.
static java.lang.String toString(int[] s)
          Describe toString method here.
static int[][][] youngTableaux(int[] s)
          Gives the pair of int[][] Young tableaux associated with the int[] permutation.
 
Methods inherited from class java.lang.Object
, clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Constructor Detail

Permutation

public Permutation()
Method Detail

identity

public static int[] identity(int len)
Returns an identity permutation of the desired length.
Parameters:
len - an int value
Returns:
an int[] value

identity

public static void identity(int[] s)
Replaces the int[] parameter with the identity of the same length.
Parameters:
s - an int[] value

random

public static int[] random(int len)
Returns a random permutation on the letters 0..len-1.
Parameters:
len - an int value
Returns:
an int[] value

random

public static int[] random(int len,
                           int derangement)
Returns a random permutation on the letters 0..len-1. If derangement is non zero, the result will be without fixed point.
Parameters:
len - an int value
derangement - an int value
Returns:
an int[] value

random

public static void random(int[] s)
Replaces the parameter array with a random array on the letters 0..len-1 where len=s.length.
Parameters:
s - an int[] value

random

public static void random(int[] s,
                          int derangement)
Replaces the parameter array with a random array on the letters 0..len-1 where len=s.length. If the second parameter is non zero, the result is a derangement, that is a permutation with no fixed point.
Parameters:
s - an int[] value
derangement - an int value

isPermutation

public static boolean isPermutation(int[] p)
Returns whether the given int[] is a valid permutation of the indices 0..length-1.
Parameters:
p - an int[] value
Returns:
a boolean value
See Also:
isPermutation(int[] p, boolean[] flags)

isPermutation

public static boolean isPermutation(int[] p,
                                    int[] garbage)
Returns whether the given int[] is a valid permutation of the indices 0..length-1. Uses the garbage int[] instance as a flag. Its values are altered and it has to be different from p.
Parameters:
p - an int[] value
garbage - an int[] of at least the same length.
Returns:
a boolean value

isPermutation

public static boolean isPermutation(int[] p,
                                    boolean[] flags)
Returns whether the given int[] is a valid permutation of the indices 0..length-1. Uses the flags boolean[] instance. Its value is altered.
Parameters:
p - an int[] value
flags - a boolean[] of at least the same length.
Returns:
a boolean value

isDerangement

public static boolean isDerangement(int[] p)
Returns whether the given int[] is a valid derangement (permutation without fixed point) of the indices 0..length-1.
Parameters:
p - an int[] value
Returns:
a boolean value
See Also:
isDerangement(int[] p, boolean[] flags)

isDerangement

public static boolean isDerangement(int[] p,
                                    int[] garbage)
Returns whether the given int[] is a valid derangement (permutation without fixed point) of the indices 0..length-1. Uses the garbage int[] instance as a flag. Its values are altered and it has to be different from p.
Parameters:
p - an int[] value
garbage - an int[] of at least the same length.
Returns:
a boolean value

isDerangement

public static boolean isDerangement(int[] p,
                                    boolean[] flags)
Returns whether the given int[] is a valid derangement (permutation without fixed point) of the indices 0..length-1. Uses the flags boolean[] instance. Its value is altered.
Parameters:
p - an int[] value
flags - a boolean[] of at least the same length.
Returns:
a boolean value

cycles

public static int[][] cycles(int[] s)
Returns the cycles of a given permutation, as int arrays.
Parameters:
s - The int[] permutation.
Returns:
The int[][] giving the array of cycles.

cyclesFun

public static int[][] cyclesFun(int[] s)
Returns the cycles of a given permutation understood as a function of the indices, as int arrays.
Parameters:
s - The int[] permutation.
Returns:
The int[][] giving the array of cycles.

fromCycles

public static void fromCycles(int[][] c,
                              int[] result)
                       throws java.lang.ArrayIndexOutOfBoundsException
Changes result to a permutation of the same length, built from the given cycles. Cycles of length 1 don't have to be included.
Parameters:
c - an int[][] value
result - an int[] value
Throws:
java.lang.ArrayIndexOutOfBoundsException - if an error occurs

fromCyclesFun

public static void fromCyclesFun(int[][] c,
                                 int[] result)
                          throws java.lang.ArrayIndexOutOfBoundsException
Changes result to a permutation of the same length, built from the given cycles, as a function of the indices. Cycles of length 1 don't have to be included.
Parameters:
c - an int[][] value
result - an int[] value
Throws:
java.lang.ArrayIndexOutOfBoundsException - if an error occurs

fromCycles

public static int[] fromCycles(int[][] c)
Returns a permutation built from its cycles. Fixed points have to be included.
Parameters:
c - an int[][] value
Returns:
an int[] value

inverse

public static int[] inverse(int[] s)
Returns the inverse permutation. It is the int[] p such that the index of i in s is p[i].
Parameters:
s - an int[] value
Returns:
an int[] value

inverse

public static void inverse(int[] s,
                           int[] result)
                    throws java.lang.IllegalArgumentException
Changes result to the inverse permutation of s. It is the int[] result such that the index of i in s is result[i]. No checks are performed to test whether the parameter was indeed a permutation, but may throw IllegalArgumentException's if it was not.
Parameters:
s - an int[] value
result - an int[] of the same (or greater) length. Has to be different from s.

numTranspos

public static int numTranspos(int[] p)
Each permutation can be written as a product of transpositions. Each cycle in the #cycle decomposition gives rise to an independant product of transposition. The cycle {2,3,...,n,1} can be written as the composition of n-1 transpositions: (1,n)(1,n-1)...(1,2). This method returns the minimal total number of required transpositions.
Parameters:
p - an int[] value
Returns:
an int value

numTranspos

public static int numTranspos(int[] p,
                              int[] garbage)
Same as numTranspos(int[]) but uses a preinstanciated int[] of length at least the length of p. It will be filled with 1.
Parameters:
p - an int[] value
garbage - an int[] such that garbage.length >= p.length.
Returns:
an int value

numTranspos

public static int numTranspos(int[] p,
                              boolean[] flags)
Describe numTranspos method here.
Parameters:
p - an int[] value
flags - a boolean[] value
Returns:
an int value

numInversions

public static int numInversions(int[] p)
Each permutation can be written as a product of transpositions of consecutive elements. This method returns the minimal total number of required transpositions, sum of the elements in the inversions(int[]) vector.
Parameters:
p - an int[] value
Returns:
an int value

parity

public static int parity(int[] p)
Gives the parity of the number of transpositions.
Parameters:
p - an int[] value
Returns:
an int value
See Also:
numInversions(int[])

order

public static int order(int[] p)
Returns the order of the given permutation. It is the least number d such that p^d=Id.
Parameters:
p - an int[] permutation.
Returns:
Its order

order

public static int order(int[] p,
                        int[] garbage)
Same as order(int[]) but uses a preinstanciated int[] of length at least the length of p. It will be filled with 1.
Parameters:
p - an int[] value
garbage - an int[] such that garbage.length >= p.length.
Returns:
an int value

order

public static int order(int[] p,
                        boolean[] flags)
Describe order method here.
Parameters:
p - an int[] value
flags - a boolean[] value
Returns:
an int value

lcm

public static int lcm(int m,
                      int n)
Computes the least common multiple of two numbers. This should definitely belong elsewhere!
Parameters:
m - An int value
n - An int value
Returns:
Their least common multiple.

gcd

public static int gcd(int m,
                      int n)
Computes the greatest common divisor of two numbers. This should definitely belong elsewhere!
Parameters:
m - An int value
n - An int value
Returns:
The greatest integer that divides them both.

lcm

public static int lcm(int[] nums)
Computes the least common multiple of several numbers.
Parameters:
nums - an int[] value
Returns:
an int value

gcd

public static int gcd(int[] nums)
Computes the greatest common divisor of several numbers.
Parameters:
nums - an int[] value
Returns:
an int value

factorial

public static int factorial(int n)
factorial(n)=n!=n*(n-1)*...*1. It is the number of permutations on n letters.
Parameters:
n - an int value
Returns:
an int value

subFactorial

public static int subFactorial(int n)
subFactorial(n+1)=!(n+1)=n*(!n+!(n-1))=[n!/E]. It is the number of deplacements on n letters.
Parameters:
n - an int value
Returns:
an int value

next

public static void next(int[] p)
Replaces a permutation with the next permutation in the cyclic lexicographic order. If you want to iterate on all permutations of a given size n, begin with a permutation and call n! times this method.
Parameters:
p - an int[] value
See Also:
factorial(int)

nextDerangement

public static void nextDerangement(int[] p)
Replaces a derangement (permutation with no fixed point) with the next derangement in the cyclic lexicographic order. If you want to iterate on all derangements of a given size n, begin with a permutation and call !n times this method.
Parameters:
p - an int[] derangement (not checked!).
See Also:
subFactorial(int), firstDerangement(int[])

firstDerangement

public static void firstDerangement(int[] p)
Let the parameter be the firstDerangement (permutation without fixed point) in the lexicographic order.
Parameters:
p - an int[] value

flipLR

public static void flipLR(int[] s)
Flips the permutation left-right.
Parameters:
s - an int[] value

flipUD

public static void flipUD(int[] s)
Flips the permutation up-down. s[i]=s.length-1-s[i].
Parameters:
s - an int[] value

previous

public static void previous(int[] p)
The previous one in the lexicographic order. Conjugates next(int[]) by flipUD(int[]).
Parameters:
p - an int[] value

applyTo

public static int applyTo(int[] s,
                          int i)
Returns j such that s[j]==i. Same as inverse(int[])(s)[i]. Beware that permutations are not in the functional format but its inverse.
Parameters:
s - an int[] value
i - an int value
Returns:
an int value
See Also:
applyToFun(int[], int)

applyToFun

public static int applyToFun(int[] s,
                             int i)
Returns s[i]. Beware that permutations are not in the functional format but its inverse.
Parameters:
s - an int[] value
i - an int value
Returns:
an int value
See Also:
applyTo(int[], int)

times

public static int[] times(int[] p1,
                          int[] p2)

times

public static void times(int[] p1,
                         int[] p2,
                         int[] result)
Composes two permutations. Gives back p2[p1[i]] and not p1[p2[i]] since the permutation notation is contra-functional. Consider timesFun(int[], int[]) for the functional notation composition.
Parameters:
p1 - an int[] permutation.
p2 - an int[] permutation of the same length.
result - an int[] of the same (or greater) length that will hold the result.
See Also:
timesInverse(int[], int[]), timesFun(int[], int[])

timesInverse

public static int[] timesInverse(int[] p1,
                                 int[] p2)

timesInverse

public static void timesInverse(int[] p1,
                                int[] p2,
                                int[] result)
Composes two permutations as functions and returns the permutation (contra-functional) notation in result. It is the same as inverse(int[])(result) after times(int[], int[])(inverse(int[])(p1),inverse(int[])(p2),result).
Parameters:
p1 - an int[] permutation.
p2 - an int[] permutation of the same length.
result - an int[] of the same (or greater) length that will hold the result.
See Also:
timesFun(int[], int[])

timesFun

public static int[] timesFun(int[] p1,
                             int[] p2)

timesFun

public static void timesFun(int[] p1,
                            int[] p2,
                            int[] result)
Returns p1[p2[i]] in result.
Parameters:
p1 - an int[] permutation.
p2 - an int[] permutation of the same length.
result - an int[] of the same (or greater) length that will hold the result.

divide

public static int[] divide(int[] p1,
                           int[] p2)

divide

public static void divide(int[] p1,
                          int[] p2,
                          int[] result)
Puts p1 composed with inverse(int[])(p2) into the third argument. Beware that the permutation notation is contra-functional. Not well optimised.
Parameters:
p1 - an int[] permutation.
p2 - an int[] permutation of the same length.
result - an int[] of the same (or greater) length that will hold the result.
See Also:
divideFun(int[], int[])

divideFun

public static int[] divideFun(int[] p1,
                              int[] p2)

divideFun

public static void divideFun(int[] p1,
                             int[] p2,
                             int[] result)
Puts p1[p2^-1[i]] into the third argument.
Parameters:
p1 - an int[] permutation.
p2 - an int[] permutation of the same length.
result - an int[] of the same (or greater) length that will hold the result.
See Also:
divideFun(int[], int[])

inversions

public static int[] inversions(int[] s)
Gives the inversion vector, that is, for each index, the number of greater indices to its left in the permutation.
Parameters:
s - an int[] value
Returns:
an int[] value

inversions

public static void inversions(int[] s,
                              int[] result)
Gives the inversion vector, that is, for each index, the number of greater indices to its left in the permutation.
Parameters:
s - an int[] value
result - an int[] of the same (or greater) length that will hold the result.

inversionsFun

public static int[] inversionsFun(int[] s)
Gives the inversion vector of a permutation in functional notation, that is, for each index, the number of greater indices to its left in the permutation.
Parameters:
s - an int[] value
Returns:
an int[] value

inversionsFun

public static void inversionsFun(int[] s,
                                 int[] result)
Gives the inversion vector of a permutation in functional notation, that is, for each index, the number of greater indices to its left in the permutation.
Parameters:
s - an int[] value
result - an int[] of the same (or greater) length that will hold the result.

fromInversions

public static int[] fromInversions(int[] inv)
Returns the permutation having inv as its inversions vector.
Parameters:
inv - an int[] value
Returns:
an int[] value

fromInversions

public static void fromInversions(int[] inv,
                                  int[] s)
Returns the permutation having inv as its inversions vector.
Parameters:
inv - an int[] value
s - the int[] result, has to be of the same (or greater) length.

fromInversionsFun

public static int[] fromInversionsFun(int[] inv)
Returns the permutation, in functional notation, having inv as its inversions vector.
Parameters:
inv - an int[] value
Returns:
an int[] value

fromInversionsFun

public static void fromInversionsFun(int[] inv,
                                     int[] s)
Returns the permutation, in functional notation, having inv as its inversions vector. It is the inverse permutation of fromInversions with the same inversion vector.
Parameters:
inv - an int[] value
s - the int[] result, has to be of the same (or greater) length.

youngTableaux

public static int[][][] youngTableaux(int[] s)
Gives the pair of int[][] Young tableaux associated with the int[] permutation. Schensted's correspondance.
Parameters:
s - an int[] value
Returns:
an int[][][] value

fromYoungTableaux

public static int[] fromYoungTableaux(int[][][] y)
Gives the pair of int[][] Young tableaux associated with the int[] permutation. Schensted's correspondance.
Parameters:
inv - an int[] value
Returns:
an int[][][] value

runs

public static int[][] runs(int[] s)
Returns the runs of a given permutation, as int arrays. It consists of increasing subsequences. I don't know what it's good for.
Parameters:
p - an int[] value
Returns:
The int[][] giving the array of runs.

cyclesToString

public static java.lang.String cyclesToString(int[] s)
Returns the cycles(int[]) view of the permutation as a String.
Parameters:
s - an int[] permutation
Returns:
a String value

cyclesToString

public static java.lang.String cyclesToString(int[][] c)
Returns the cycles(int[]) view of the permutation as a String. Doesn't check for validity, any int[][] will do.
Parameters:
c - an int[][], supposedly the cycles of a permutation.
Returns:
a String value

stringToCycles

public static final int[][] stringToCycles(java.lang.String s)
Hands back an int[][] coded by a string. () are considered as separating the different arrays. Creates a temporary int[] value big enough to hold all the int's. Describe stringToCycles method here.
Parameters:
s - a String value
Returns:
an int[][] value

stringToIntArray

public static int[] stringToIntArray(java.lang.String s)
Hands back an integer array coded by a string. Space, tab, () ,;: {} are considered as white spaces. Creates a temporary int[] value big enough to hold all the int's.
Parameters:
s - a String value
Returns:
an int[] value
See Also:
stringToIntArray(String,int[])

stringToIntArray

public static int[] stringToIntArray(java.lang.String s,
                                     int[] basket)
Hands back an integer array coded by a string. Space, tab, () ,;: {} are considered as white spaces.
Parameters:
s - a String value
basket - a temporary int[] value big enough to hold all the int's.
Returns:
an int[] value

toString

public static java.lang.String toString(int[] s)
Describe toString method here.
Returns:
a String value