Class Permutation

java.lang.Object
org.bzdev.math.Permutation

public class Permutation extends Object
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)
    0   1   2  ...   n-1
 (                        )
   p_1 p_2 p_3 ... p_{n-1}
 
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.

The permutation itself can be defined by a vector providing the values

 p_1, p_2, p_3, ... p_{n-1}
 
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 by
    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

    Constructors
    Constructor
    Description
    Permutation(int n)
    Constructor for an identity permutation
    Permutation(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 Type
    Method
    Description
    double[]
    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
    Get the size of the permutation.
    int[]
    Get the vector that defines a permutation.
    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.

    Methods inherited from class java.lang.Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
  • 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 cycle
      n - 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
          0 1 2 3 4 5 6 7 8
       (                    )
          0 1 3 4 2 5 6 7 8
       
      to
          0 1 2 3 4 5 6 7 8
       (                    ).
          1 0 3 4 2 5 6 7 8
       
      Parameters:
      i - the first index
      j - 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 permute
      dest - 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

      public void applyTo(double[][] src, double[][] dest) throws IllegalArgumentException
      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 permute
      dest - a vector that will contain the permuted values
      Throws:
      IllegalArgumentException - arguments not compatible
      NullPointerException - 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 permute
      result - the matrix AP, which must have the same dimensions as A
      aT - 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

      public Permutation applyTo(Permutation p)
      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

      public Permutation inverse()
      Get the inverse permutation. The inverse has the property that for a permutation p and a vector v, v equals
      p.inverse().applyTo(p.applyTo(v)).
      Returns:
      the inverse permutation