java.lang.Object
org.bzdev.math.Permutation
Permutation class.
A permutation (as supported by this class) is a one-to-one mapping of the
set of integers [0,n-1] onto itself. It can be represented by the
notation (drawn so that the parentheses cover both lines)
where the top line gives values in the mapping's domain and the bottom line gives the corresponding value in the mapping's range. This is sometimes abbreviated by providing just the bottom line values separated by commas. When applied to a vector v1, the result is a vector v2 of the same size whose value v2[i] = v1[p_i] where p_i is the value in the permutation's range corresponding to a value i in the permutation's domain.0 1 2 ... n-1 ( ) p_1 p_2 p_3 ... p_{n-1}
The permutation itself can be defined by a vector providing the values
or by providing the permutation's cycles. The cycle notation represents a permutation as the concatenation of cyclic permutations. Each cycle is defined as a list of numbers delimited by parentheses and separated by spaces. For each adjacent pair, and for the implicit pair consisting of the last element followed by the first, the first (or left-hand) element in the pair corresponds to an entry in the top line using two-line notation and the second (or right-hand) element corresponds to the matching entry in the bottom line. Thus (2 3 4) denotes the permutation (for n = 8) given byp_1, p_2, p_3, ... p_{n-1}
0 1 2 3 4 5 6 7 8 ( ) 0 1 3 4 2 5 6 7 8
A permutation matrix is the matrix produced by applying a permutation to the rows of the identity matrix. The resulting matrix has precisely one '1' in each row and column with the other elements equal to zero. The matrix product PA thus applies the permutation to the rows of A and the matrix product AP applies the permutation's inverse to the columns of A.
-
Constructor Summary
ConstructorsConstructorDescriptionPermutation
(int n) Constructor for an identity permutationPermutation
(int[] vector) Constructor.Permutation
(int[][] matrix) Construct a permutation given its matrix.Permutation
(int[][] cycles, int n) Constructor given a permutation's cycles The permutation's domain is the set of integers [0, n), and the integer arrays denoting each cycle contain the values of the cycle in the same order as in cycle notation. -
Method Summary
Modifier and TypeMethodDescriptiondouble[]
applyTo
(double[] vector) Apply a permutation to a vector.double[][]
applyTo
(double[][] A) Apply a permutation to a matrix.void
applyTo
(double[][] src, double[][] dest) Applies a permutation to a matrix and store the results.void
applyTo
(double[] src, double[] dest) Applies a permutation to a vector and store the results.Apply one permutation to another.double
det()
Get the determinate of the permutation's matrix.int[][]
Get a permutation's cycles An array defining a cycle contains the cycle in the same order as in cycle notation.double[][]
Get a permutation's matrix.int
getSize()
Get the size of the permutation.int[]
Get the vector that defines a permutation.inverse()
Get the inverse permutation.double[][]
leftMultiplyBy
(double[][] A) Left-multiply this permutation's matrix by a matrix A and return the results as a newly allocated matrix.void
leftMultiplyBy
(double[][] A, double[][] result, double[][] aT) /** Left-multiply a permutation's matrix by a matrix A.void
swap
(int i, int j) Modify a permutation by applying a cyclic permutation whose cycle length is 2.
-
Constructor Details
-
Permutation
public Permutation(int n) Constructor for an identity permutation- Parameters:
n
- the number of integers
-
Permutation
public Permutation(int[] vector) Constructor. The values of the vector provided as an argument correspond to the bottom line in two-line notation.- Parameters:
vector
- an array listing the permuted values of the integers [0,n), where n is the length of the vector
-
Permutation
public Permutation(int[][] matrix) Construct a permutation given its matrix.- Parameters:
matrix
- the permutation matrix
-
Permutation
public Permutation(int[][] cycles, int n) Constructor given a permutation's cycles The permutation's domain is the set of integers [0, n), and the integer arrays denoting each cycle contain the values of the cycle in the same order as in cycle notation. Thus, (2 4 5) could be represented by an integer array with an initializer {2, 4, 5}.- Parameters:
cycles
- an array of a permutation's cycles, each element of which is an integer array representing a cyclen
- the number of integers in the permutation
-
-
Method Details
-
getVector
public int[] getVector()Get the vector that defines a permutation.- Returns:
- the vector defining this permutation
-
getCycles
public int[][] getCycles()Get a permutation's cycles An array defining a cycle contains the cycle in the same order as in cycle notation.- Returns:
- an array of integer arrays, each of which defines a cycle
-
det
public double det()Get the determinate of the permutation's matrix.- Returns:
- the determinate
-
getSize
public int getSize()Get the size of the permutation. This is the number of integers over which the permutation is defined.- Returns:
- the size of the permutation
-
getMatrix
public double[][] getMatrix()Get a permutation's matrix. The matrix is defined so that PV, where P is the permutation matrix and V is vector, returns a vector whose values for an index i are the value of V at an index equal to the value to which the permutation maps the index i. I.e., the value of PV for index i is equal to V[pvector[i]] where pvector is the permutation's vector.- Returns:
- the matrix
-
swap
public void swap(int i, int j) Modify a permutation by applying a cyclic permutation whose cycle length is 2. The new permutation is the result of applying a permutation consisting of the cycle (i j) to the old permutation. Thus (0 1) changes
to0 1 2 3 4 5 6 7 8 ( ) 0 1 3 4 2 5 6 7 8
0 1 2 3 4 5 6 7 8 ( ). 1 0 3 4 2 5 6 7 8
- Parameters:
i
- the first indexj
- the second index
-
applyTo
public double[] applyTo(double[] vector) Apply a permutation to a vector.- Parameters:
vector
- the vector to permute- Returns:
- a new vector containing the permuted values
-
applyTo
public void applyTo(double[] src, double[] dest) Applies a permutation to a vector and store the results. The vectors src and dest can be identical. Given the permutation's vector pvector, after the call completes, dest[i] = src[pvector[i]] for i in [0,n).- Parameters:
src
- the vector to permutedest
- a vector that will contain the permuted values
-
applyTo
public double[][] applyTo(double[][] A) Apply a permutation to a matrix. The rows of the matrix are permuted, not the columns. If P is the permutation's matrix, the result is the matrix product PA.- Parameters:
A
- the matrix to permute- Returns:
- a new matrix containing the permuted values
- See Also:
-
applyTo
Applies a permutation to a matrix and store the results. Rows are permuted, not columns. The matrices src and dest can be identical. If P is the permutation's matrix, D is the destination, and S is the source, then after the call completes, D = PS. I.e., given the permutation's vector pvector, after the call completes, dest[i] = src[pvector[i]] for i in [0,n).- Parameters:
src
- the vector to permutedest
- a vector that will contain the permuted values- Throws:
IllegalArgumentException
- arguments not compatibleNullPointerException
- an argument was null
-
leftMultiplyBy
public void leftMultiplyBy(double[][] A, double[][] result, double[][] aT) /** Left-multiply a permutation's matrix by a matrix A. If P is the permutation's matrix and given the argument A, the resulting matrix is AP. The result is the inverse permuation applied to A's columns. The implementation uses the fact that AP = ((AP)T)T = (PTAT)T = (P-1AT)T If the dimensions of A and result are n by m, the dimensions of aT must be m by n, and regardless, it must be true that n > 0 and m > 0.- Parameters:
A
- the matrix to permuteresult
- the matrix AP, which must have the same dimensions as AaT
- a work area sized to store the transpose of A, whose dimensions are those for A's transpose.
-
leftMultiplyBy
public double[][] leftMultiplyBy(double[][] A) Left-multiply this permutation's matrix by a matrix A and return the results as a newly allocated matrix. This applies the inverse permutation to the columns of A. Permute the columns of a matrix, returning the new matrix. If P is the permutation's matrix and given the argument A, the resulting matrix is AP. The implementation uses the fact that AP = ((AP)T)T = (PTAT)T = (P-1AT)T- Parameters:
A
- the matrix to permute- Returns:
- a matrix with permuted columns
-
applyTo
Apply one permutation to another. The permutation vector of the argument is permuted by this permutation and that permuted vector is used to construct a new permutation.- Parameters:
p
- a permutation- Returns:
- a new permutation such that its vector is this permutation of p's vector
-
inverse
Get the inverse permutation. The inverse has the property that for a permutation p and a vector v, v equalsp.inverse().applyTo(p.applyTo(v)).
- Returns:
- the inverse permutation
-