cc.redberry.core.groups.permutations

Class Permutations

java.lang.Object

cc.redberry.core.groups.permutations.Permutations

public final class Permutations
extends java.lang.Object

Static methods to operate with permutations.

Since:

1.1.6

Field Summary

Fields

Modifier and Type	Field and Description
static int	DEFAULT_IDENTITY_LENGTH Default (optimal for average problem) value of identity permutation length

Method Summary

Modifier and Type	Method and Description
static int[]	convertCyclesToOneLine(int[][] cycles) Converts cycles to one-line notation.
static int[][]	convertOneLineToCycles(byte[] permutation) Converts permutation written in one-line notation to disjoint cycles notation.
static int[][]	convertOneLineToCycles(int[] permutation) Converts permutation written in one-line notation to disjoint cycles notation.
static int[][]	convertOneLineToCycles(short[] permutation) Converts permutation written in one-line notation to disjoint cycles notation.
static int[]	createBlockCycle(int blockSize, int numberOfBlocks)
static int[]	createBlockTransposition(int length1, int length2)
static int[]	createCycle(int dimension) Creates cycle permutation written in one-line notation, i.e.
static int[]	createIdentityArray(int length) Creates array that represents identity one-line permutation of specified degree.
static Permutation	createIdentityPermutation(int degree) Creates identity permutation with with specified degree.
static Permutation	createPermutation(boolean antisymmetry, int... oneLine) Creates permutation instance from a given array that represents permutation in one-line notation.
static Permutation	createPermutation(boolean antisymmetry, int[][] cycles) Creates permutation instance from a given array that represents permutation in disjoint cycle notation.
static Permutation	createPermutation(int... oneLine) Creates permutation instance from a given array that represents permutation in one-line notation.
static Permutation	createPermutation(int[][] cycles) Creates permutation instance from a given array that represents permutation in disjoint cycle notation.
static int[]	createTransposition(int dimension) Creates transposition of first two elements written in one-line notation with specified dimension, i.e.
static int[]	createTransposition(int dimension, int position1, int position2) Creates transposition in one-line notation
static Permutation	getIdentityPermutation() Returns identity permutation.
static IntArrayList	getOrbitList(java.util.Collection<Permutation> generators, int point, int degree) Returns an orbit of specified point
static IntArrayList	getOrbitList(java.util.List<Permutation> generators, int point) Returns an orbit of specified point
static int	getOrbitSize(java.util.List<Permutation> generators, int point) Returns a size of specified point orbit
static int	getOrbitSize(java.util.List<Permutation> generators, int point, int degree) Returns a size of specified point orbit
static int[]	getRandomSortedDistinctArray(int minValue, int maxvalue, int length, org.apache.commons.math3.random.RandomGenerator generator)
static byte	internalDegree(byte[] permutation) Calculates degree of permutation, i.e.larges point moved by specified permutation plus one.
static int	internalDegree(int[] permutation) Calculates degree of permutation, i.e.larges point moved by specified permutation plus one.
static int	internalDegree(java.util.List<? extends Permutation> permutations) Calculates common degree of specified permutations, i.e.larges point moved by specified permutations plus one.
static short	internalDegree(short[] permutation) Calculates degree of permutation, i.e.larges point moved by specified permutation plus one.
static int[]	inverse(int[] permutation) Returns the inverse permutation for the specified one.
static boolean	isIdentity(byte[] permutation) Returns true if specified permutation, written in one-line notation, is identity and false otherwise.
static boolean	isIdentity(int[] permutation) Returns true if specified permutation, written in one-line notation, is identity and false otherwise.
static boolean	isIdentity(short[] permutation) Returns true if specified permutation, written in one-line notation, is identity and false otherwise.
static int[]	lengthsOfCycles(byte[] permutation) Returns an array of cycles lengths.
static int[]	lengthsOfCycles(int[] permutation) Returns an array of cycles lengths.
static int[]	lengthsOfCycles(short[] permutation) Returns an array of cycles lengths.
static int[][]	orbits(java.util.List<Permutation> generators, int[] positionsInOrbit) Calculates orbits of specified generators.
static java.math.BigInteger	orderOfPermutation(byte[] permutation) Calculates the order of specified permutation.
static java.math.BigInteger	orderOfPermutation(int[] permutation) Calculates the order of specified permutation.
static java.math.BigInteger	orderOfPermutation(short[] permutation) Calculates the order of specified permutation.
static boolean	orderOfPermutationIsOdd(byte[] permutation) Returns true if order of specified permutation is odd and false otherwise.
static boolean	orderOfPermutationIsOdd(int[] permutation) Returns true if order of specified permutation is odd and false otherwise.
static boolean	orderOfPermutationIsOdd(short[] permutation) Returns true if order of specified permutation is odd and false otherwise.
static int	parity(byte[] permutation) Calculates parity of specified permutation
static int	parity(int[] permutation) Calculates parity of specified permutation
static int	parity(short[] permutation) Calculates parity of specified permutation
static int[]	permute(int[] array, int[] permutation) Permutes specified array according to specified permutation and returns the result.
static <T> java.util.List<T>	permute(java.util.List<T> array, int[] permutation) Permutes specified list according to specified permutation and returns the result.
static <T> T[]	permute(T[] array, int[] permutation) Permutes specified array according to specified permutation and returns the result.
static int[]	randomPermutation(int n) Creates random permutation of specified dimension
static int[]	randomPermutation(int n, org.apache.commons.math3.random.RandomGenerator rnd) Creates random permutation of specified dimension
static void	shuffle(int[] a) Randomly permutes the specified array.
static void	shuffle(int[] a, org.apache.commons.math3.random.RandomGenerator rnd) Randomly permutes the specified list using the specified source of randomness.
static void	shuffle(java.lang.Object[] a) Randomly permute the specified list using the specified source of randomness.
static void	shuffle(java.lang.Object[] a, org.apache.commons.math3.random.RandomGenerator rnd) Randomly permutes the specified list using the specified source of randomness.
static boolean	testPermutationCorrectness(byte[] permutation) Tests whether the specified array satisfies the one-line notation for permutations
static boolean	testPermutationCorrectness(byte[] permutation, boolean sign) Tests whether the specified array satisfies the one-line notation for permutations and in case of negative sign that its order is even
static boolean	testPermutationCorrectness(int[] permutation) Tests whether the specified array satisfies the one-line notation for permutations
static boolean	testPermutationCorrectness(int[] permutation, boolean sign) Tests whether the specified array satisfies the one-line notation for permutations and in case of negative sign that its order is even
static boolean	testPermutationCorrectness(short[] permutation) Tests whether the specified array satisfies the one-line notation for permutations
static boolean	testPermutationCorrectness(short[] permutation, boolean sign) Tests whether the specified array satisfies the one-line notation for permutations and in case of negative sign that its order is even

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

DEFAULT_IDENTITY_LENGTH

public static final int DEFAULT_IDENTITY_LENGTH

Default (optimal for average problem) value of identity permutation length

See Also:

Constant Field Values

Method Detail

internalDegree

public static int internalDegree(int[] permutation)

Calculates degree of permutation, i.e.larges point moved by specified permutation plus one.

Parameters:

permutation - permutation

Returns:

larges point moved by specified permutation plus one

internalDegree

public static short internalDegree(short[] permutation)

Calculates degree of permutation, i.e.larges point moved by specified permutation plus one.

Parameters:

permutation - permutation

Returns:

larges point moved by specified permutation plus one

internalDegree

public static byte internalDegree(byte[] permutation)

Calculates degree of permutation, i.e.larges point moved by specified permutation plus one.

Parameters:

permutation - permutation

Returns:

larges point moved by specified permutation plus one

internalDegree

public static int internalDegree(java.util.List<? extends Permutation> permutations)

Calculates common degree of specified permutations, i.e.larges point moved by specified permutations plus one.

Parameters:

permutations - permutations

Returns:

larges point moved by specified permutations plus one

parity

public static int parity(int[] permutation)

Calculates parity of specified permutation

Parameters:

permutation - permutation

Returns:

parity of permutation

parity

public static int parity(short[] permutation)

Calculates parity of specified permutation

Parameters:

permutation - permutation

Returns:

parity of permutation

parity

public static int parity(byte[] permutation)

Calculates parity of specified permutation

Parameters:

permutation - permutation

Returns:

parity of permutation

isIdentity

public static boolean isIdentity(int[] permutation)

Returns true if specified permutation, written in one-line notation, is identity and false otherwise.

Parameters:

permutation - permutation in one-line notation

Returns:

true if specified permutation is identity and false otherwise

isIdentity

public static boolean isIdentity(short[] permutation)

Returns true if specified permutation, written in one-line notation, is identity and false otherwise.

Parameters:

permutation - permutation in one-line notation

Returns:

true if specified permutation is identity and false otherwise

isIdentity

public static boolean isIdentity(byte[] permutation)

Returns true if specified permutation, written in one-line notation, is identity and false otherwise.

Parameters:

permutation - permutation in one-line notation

Returns:

true if specified permutation is identity and false otherwise

testPermutationCorrectness

public static boolean testPermutationCorrectness(int[] permutation,
                                                 boolean sign)

Tests whether the specified array satisfies the one-line notation for permutations and in case of negative sign that its order is even

Parameters:

permutation - array to be tested

Returns:

true if specified array satisfies the one-line notation for permutations and if sign is true that its order is even

testPermutationCorrectness

public static boolean testPermutationCorrectness(short[] permutation,
                                                 boolean sign)

Tests whether the specified array satisfies the one-line notation for permutations and in case of negative sign that its order is even

Parameters:

permutation - array to be tested

Returns:

true if specified array satisfies the one-line notation for permutations and if sign is true that its order is even

testPermutationCorrectness

public static boolean testPermutationCorrectness(byte[] permutation,
                                                 boolean sign)

Tests whether the specified array satisfies the one-line notation for permutations and in case of negative sign that its order is even

Parameters:

permutation - array to be tested

Returns:

true if specified array satisfies the one-line notation for permutations and if sign is true that its order is even

testPermutationCorrectness

public static boolean testPermutationCorrectness(int[] permutation)

Tests whether the specified array satisfies the one-line notation for permutations

Parameters:

permutation - array to be tested

Returns:

true if specified array satisfies the one-line notation for permutations and false if not

testPermutationCorrectness

public static boolean testPermutationCorrectness(short[] permutation)

Tests whether the specified array satisfies the one-line notation for permutations

Parameters:

permutation - array to be tested

Returns:

true if specified array satisfies the one-line notation for permutations and false if not

testPermutationCorrectness

public static boolean testPermutationCorrectness(byte[] permutation)

Tests whether the specified array satisfies the one-line notation for permutations

Parameters:

permutation - array to be tested

Returns:

true if specified array satisfies the one-line notation for permutations and false if not

orderOfPermutation

public static java.math.BigInteger orderOfPermutation(int[] permutation)

Calculates the order of specified permutation. Since the maximum order g(n) of permutation in symmetric group S(n) is about log(g(n)) <= sqrt(n log(n))* (1 + log log(n) / (2 log(n))), then g(n) can be very big (e.g. for n = 1000, g(n) ~1e25). The algorithm decomposes permutation into product of cycles and returns l.c.m. of their sizes.

Parameters:

permutation -

Returns:

order of specified permutation

orderOfPermutation

public static java.math.BigInteger orderOfPermutation(short[] permutation)

Calculates the order of specified permutation. Since the maximum order g(n) of permutation in symmetric group S(n) is about log(g(n)) <= sqrt(n log(n))* (1 + log log(n) / (2 log(n))), then g(n) can be very big (e.g. for n = 1000, g(n) ~1e25). The algorithm decomposes permutation into product of cycles and returns l.c.m. of their sizes.

Parameters:

permutation -

Returns:

order of specified permutation

orderOfPermutation

public static java.math.BigInteger orderOfPermutation(byte[] permutation)

Calculates the order of specified permutation. Since the maximum order g(n) of permutation in symmetric group S(n) is about log(g(n)) <= sqrt(n log(n))* (1 + log log(n) / (2 log(n))), then g(n) can be very big (e.g. for n = 1000, g(n) ~1e25). The algorithm decomposes permutation into product of cycles and returns l.c.m. of their sizes.

Parameters:

permutation -

Returns:

order of specified permutation

orderOfPermutationIsOdd

public static boolean orderOfPermutationIsOdd(int[] permutation)

Returns true if order of specified permutation is odd and false otherwise. This algorithm is very fast since it does not compute order of element, but calculates just its parity without use of any "hard" computations with g.c.d./l.c.m./BigInteger arithmetics etc.

Parameters:

permutation - permutation

Returns:

true if order of specified permutation is odd and false otherwise

orderOfPermutationIsOdd

public static boolean orderOfPermutationIsOdd(short[] permutation)

Returns true if order of specified permutation is odd and false otherwise. This algorithm is very fast since it does not compute order of element, but calculates just its parity without use of any "hard" computations with g.c.d./l.c.m./BigInteger arithmetics etc.

Parameters:

permutation - permutation

Returns:

true if order of specified permutation is odd and false otherwise

orderOfPermutationIsOdd

public static boolean orderOfPermutationIsOdd(byte[] permutation)

Returns true if order of specified permutation is odd and false otherwise. This algorithm is very fast since it does not compute order of element, but calculates just its parity without use of any "hard" computations with g.c.d./l.c.m./BigInteger arithmetics etc.

Parameters:

permutation - permutation

Returns:

true if order of specified permutation is odd and false otherwise

getOrbitList

public static IntArrayList getOrbitList(java.util.List<Permutation> generators,
                                        int point)

Returns an orbit of specified point

Parameters:

generators - a list of group generators

point - point

Returns:

orbit of specified point

getOrbitList

public static IntArrayList getOrbitList(java.util.Collection<Permutation> generators,
                                        int point,
                                        int degree)

Returns an orbit of specified point

Parameters:

generators - a list of group generators

point - point

degree - largest integer moved by the generators plus one or bigger

Returns:

orbit of specified point

getOrbitSize

public static int getOrbitSize(java.util.List<Permutation> generators,
                               int point,
                               int degree)

Returns a size of specified point orbit

Parameters:

generators - a list of group generators

point - point

degree - largest integer moved by the generators plus one or bigger

Returns:

size of point orbit

getOrbitSize

public static int getOrbitSize(java.util.List<Permutation> generators,
                               int point)

Returns a size of specified point orbit

Parameters:

generators - a list of group generators

point - point

Returns:

size of point orbit

orbits

public static int[][] orbits(java.util.List<Permutation> generators,
                             int[] positionsInOrbit)

Calculates orbits of specified generators.

Parameters:

generators - permutations

positionsInOrbit - an array that will be filled with the indexes in the resulting orbits, such that for any point orbits[positionsInOrbit[point]] - is orbit of this point.

Returns:

orbits

convertCyclesToOneLine

public static int[] convertCyclesToOneLine(int[][] cycles)

Converts cycles to one-line notation.

Parameters:

cycles - disjoint cycles

Returns:

permutation written in one-line notation

convertOneLineToCycles

public static int[][] convertOneLineToCycles(int[] permutation)

Converts permutation written in one-line notation to disjoint cycles notation.

Parameters:

permutation - permutation written in one-line notation

Returns:

permutation written in disjoint cycles notation

convertOneLineToCycles

public static int[][] convertOneLineToCycles(short[] permutation)

Converts permutation written in one-line notation to disjoint cycles notation.

Parameters:

permutation - permutation written in one-line notation

Returns:

permutation written in disjoint cycles notation

convertOneLineToCycles

public static int[][] convertOneLineToCycles(byte[] permutation)

Converts permutation written in one-line notation to disjoint cycles notation.

Parameters:

permutation - permutation written in one-line notation

Returns:

permutation written in disjoint cycles notation

lengthsOfCycles

public static int[] lengthsOfCycles(int[] permutation)

Returns an array of cycles lengths.

Parameters:

permutation - permutation written in one-line notation

Returns:

an array of cycles lengths

lengthsOfCycles

public static int[] lengthsOfCycles(short[] permutation)

Returns an array of cycles lengths.

Parameters:

permutation - permutation written in one-line notation

Returns:

an array of cycles lengths

lengthsOfCycles

public static int[] lengthsOfCycles(byte[] permutation)

Returns an array of cycles lengths.

Parameters:

permutation - permutation written in one-line notation

Returns:

an array of cycles lengths

randomPermutation

public static int[] randomPermutation(int n,
                                      org.apache.commons.math3.random.RandomGenerator rnd)

Creates random permutation of specified dimension

Parameters:

n - dimension

rnd - random generator

Returns:

random permutation of specified dimension

randomPermutation

public static int[] randomPermutation(int n)

Creates random permutation of specified dimension

Parameters:

n - dimension

Returns:

random permutation of specified dimension

shuffle

public static void shuffle(int[] a)

Randomly permutes the specified array.

Parameters:

a - - the array to be shuffled.

shuffle

public static void shuffle(int[] a,
                           org.apache.commons.math3.random.RandomGenerator rnd)

Randomly permutes the specified list using the specified source of randomness.

Parameters:

a - - the array to be shuffled.

rnd - - the source of randomness to use to shuffle the list.

shuffle

public static void shuffle(java.lang.Object[] a,
                           org.apache.commons.math3.random.RandomGenerator rnd)

Randomly permutes the specified list using the specified source of randomness.

Parameters:

a - - the array to be shuffled.

rnd - - the source of randomness to use to shuffle the list.

shuffle

public static void shuffle(java.lang.Object[] a)

Randomly permute the specified list using the specified source of randomness.

Parameters:

a - - the array to be shuffled.

createPermutation

public static Permutation createPermutation(boolean antisymmetry,
                                            int[][] cycles)

Creates permutation instance from a given array that represents permutation in disjoint cycle notation.

This method will automatically choose an appropriate underlying implementation of Permutation depending on the permutation length.

If order of specified permutation is odd and antisymmetry is specified, then exception will thrown, since such antisymmetry is impossible from the mathematical point of view.

Parameters:

antisymmetry - if true, then antisymmetry will be created

cycles - array of disjoint cycles

Returns:

an instance of Permutation

Throws:

java.lang.IllegalArgumentException - if specified array is inconsistent with disjoint cycle notation

java.lang.IllegalArgumentException - if antisymmetry is true and permutation order is odd

createPermutation

public static Permutation createPermutation(int[][] cycles)

Creates permutation instance from a given array that represents permutation in disjoint cycle notation.

This method will automatically choose an appropriate underlying implementation of Permutation depending on the permutation length.

Parameters:

cycles - array of disjoint cycles

Returns:

an instance of Permutation

Throws:

java.lang.IllegalArgumentException - if specified array is inconsistent with disjoint cycle notation

createPermutation

public static Permutation createPermutation(int... oneLine)

Creates permutation instance from a given array that represents permutation in one-line notation.

This method will automatically choose an appropriate underlying implementation of Permutation depending on the permutation length.

Parameters:

oneLine - array that represents permutation in one line notation

Returns:

an instance of Permutation

Throws:

java.lang.IllegalArgumentException - if specified array is inconsistent with one-line notation

createPermutation

public static Permutation createPermutation(boolean antisymmetry,
                                            int... oneLine)

Creates permutation instance from a given array that represents permutation in one-line notation.

This method will automatically choose an appropriate underlying implementation of Permutation depending on the permutation length.

If order of specified permutation is odd and antisymmetry is specified, then exception will thrown, since such antisymmetry is impossible from the mathematical point of view.

Parameters:

antisymmetry - if true, then antisymmetry will be created

oneLine - array that represents permutation in one line notation

Returns:

an instance of Permutation

Throws:

java.lang.IllegalArgumentException - if specified array is inconsistent with one-line notation

java.lang.IllegalArgumentException - if antisymmetry is true and permutation order is odd

permute

public static <T> T[] permute(T[] array,
                              int[] permutation)

Permutes specified array according to specified permutation and returns the result.

Type Parameters:

T - any type

Parameters:

array - array

permutation - permutation in one-line notation

Returns:

new array permuted with specified permutation

Throws:

java.lang.IllegalArgumentException - if array length not equals to permutation length

java.lang.IllegalArgumentException - if permutation is not consistent with one-line notation

permute

public static <T> java.util.List<T> permute(java.util.List<T> array,
                                            int[] permutation)

Permutes specified list according to specified permutation and returns the result.

Type Parameters:

T - any type

Parameters:

array - array

permutation - permutation in one-line notation

Returns:

new array permuted with specified permutation

Throws:

java.lang.IllegalArgumentException - if array length not equals to permutation length

java.lang.IllegalArgumentException - if permutation is not consistent with one-line notation

permute

public static int[] permute(int[] array,
                            int[] permutation)

Permutes specified array according to specified permutation and returns the result.

Parameters:

array - array

permutation - permutation in one-line notation

Returns:

new array permuted with specified permutation

Throws:

java.lang.IllegalArgumentException - if array length not equals to permutation length

java.lang.IllegalArgumentException - if permutation is not consistent with one-line notation

getRandomSortedDistinctArray

public static int[] getRandomSortedDistinctArray(int minValue,
                                                 int maxvalue,
                                                 int length,
                                                 org.apache.commons.math3.random.RandomGenerator generator)

createIdentityArray

public static int[] createIdentityArray(int length)

Creates array that represents identity one-line permutation of specified degree.

Parameters:

length - degree of permutation (array length)

Returns:

array that represents identity one-line permutation of specified degree

createIdentityPermutation

public static Permutation createIdentityPermutation(int degree)

Creates identity permutation with with specified degree.

Parameters:

degree - size of internal buffer of permutation

Returns:

identity permutation

getIdentityPermutation

public static Permutation getIdentityPermutation()

Returns identity permutation.

Returns:

identity permutation

createTransposition

public static int[] createTransposition(int dimension)

Creates transposition of first two elements written in one-line notation with specified dimension, i.e. an array of form [1,0,2,3,4,...,dimension - 1].

Parameters:

dimension - dimension of the resulting permutation, e.g. the array length

Returns:

transposition permutation in one-line notation

createTransposition

public static int[] createTransposition(int dimension,
                                        int position1,
                                        int position2)

Creates transposition in one-line notation

Parameters:

dimension - dimension of the resulting permutation, e.g. the array length

position1 - first position

position2 - second position

Returns:

transposition

createCycle

public static int[] createCycle(int dimension)

Creates cycle permutation written in one-line notation, i.e. an array of form [dimension-1,0,1, ...,dimension-2].

Parameters:

dimension - dimension of the resulting permutation, e.g. the array length

Returns:

cycle permutation in one-line notation

createBlockCycle

public static int[] createBlockCycle(int blockSize,
                                     int numberOfBlocks)

createBlockTransposition

public static int[] createBlockTransposition(int length1,
                                             int length2)

inverse

public static int[] inverse(int[] permutation)

Returns the inverse permutation for the specified one.

One-line notation for permutations is used.

Parameters:

permutation - permutation in one-line notation

Returns:

inverse permutation to the specified one