Module org.cicirello.jpt
Package org.cicirello.permutations

Class Permutation

java.lang.Object
org.cicirello.permutations.Permutation
All Implemented Interfaces:
Serializable, Iterable<Permutation>, Copyable<Permutation>
public final class Permutation extends Object implements Serializable, Iterable<Permutation>, Copyable<Permutation>
Representation of a permutation of the integers from 0 to N-1, inclusive. This class provides the functionality to generate random permutations, and to manipulate permutations in a variety of ways.
See Also:

  • Constructor Summary

    Constructors
    Constructor
    Description
    Permutation(int n)
    Initializes a random permutation of n integers.
    Permutation(int[] p)
    Initializes a permutation of n integers to be identical to the elements of an array.
    Permutation(int n, int value)
    Initializes a specific permutation from an integer in mixed radix form representing the chosen permutation.
    Permutation(int n, BigInteger value)
    Initializes a specific permutation from an integer in mixed radix form representing the chosen permutation.
    Permutation(int n, RandomGenerator r)
    Initializes a random permutation of n integers.
    Permutation(Permutation p)
    Initializes a permutation of n integers to be identical to a given permutation.
    Permutation(Permutation p, int length)
    Initializes a permutation of the integers in the interval [0, length) based on their relative order in a permutation p.

  • Method Summary

    Modifier and Type
    Method
    Description
    void
    apply(PermutationBinaryOperator operator, Permutation other)
    Applies a custom binary operator on a pair of Permutation objects.
    void
    apply(PermutationFullBinaryOperator operator, Permutation other)
    Applies a custom binary operator on a pair of Permutation objects.
    void
    apply(PermutationFullUnaryOperator operator)
    Applies a custom unary operator on a Permutation object.
    void
    apply(PermutationUnaryOperator operator)
    Applies a custom unary operator on a Permutation object.
    void
    applyThenValidate(PermutationBinaryOperator operator, Permutation other)
    Applies a custom binary operator on a pair of Permutation objects, and then validates the state of the Permutation.
    void
    applyThenValidate(PermutationFullBinaryOperator operator, Permutation other)
    Applies a custom binary operator on a pair of Permutation objects, and then validates the state of the Permutation.
    void
    applyThenValidate(PermutationFullUnaryOperator operator)
    Applies a custom unary operator on a Permutation object, and then validates the state of the Permutation.
    void
    applyThenValidate(PermutationUnaryOperator operator)
    Applies a custom unary operator on a Permutation object, and then validates the state of the Permutation.
    Permutation
    copy()
    Creates an identical copy of this object.
    void
    cycle(int[] indexes)
    Creates a permutation cycle from a sequence of permutation indexes.
    boolean
    equals(Object other)
    Equality test: Two permutations are equal if they are of the same length and contain the same elements in the same order.
    int
    get(int i)
    Retrieves the i-th integer of the permutation.
    int[]
    get(int i, int j)
    Retrieves a range of elements from the permutation.
    int[]
    get(int i, int j, int[] array)
    Retrieves a range of elements from the permutation.
    int[]
    getInverse()
    Computes the inverse of the permutation.
    Permutation
    getInversePermutation()
    Computes a Permutation that is the inverse of this Permutation.
    int
    hashCode()
    Uses Java's Arrays class's method for generating a hashCode from an array of ints.
    void
    invert()
    Inverts the Permutation, such that if p1 is the Permutation immediately prior to the call to invert, and if p2 is the Permutation immediately after the call to invert, then p1.get(i) == j iff p2.get(j) == i, for all i, j.
    Iterator<Permutation>
    iterator()
    Returns an Iterator over all Permutations the length of this Permutation.
    int
    length()
    Retrieves the length of the permutation.
    void
    removeAndInsert(int i, int j)
    Removes integer from one position and then inserts it into a a new position shifting the rest of the permutation as necessary.
    void
    removeAndInsert(int i, int size, int j)
    Removes a sub-array of integers from one position and then inserts it into a a new position shifting the rest of the permutation as necessary.
    void
    reverse()
    Reverses the order of the elements in the permutation.
    void
    reverse(int i, int j)
    Reverses the order of the elements of a subrange of the permutation.
    void
    rotate(int numPositions)
    Circular rotation of permutation (to the left).
    void
    scramble()
    Randomly shuffles the permutation.
    void
    scramble(boolean guaranteeDifferent)
    Randomly shuffles the permutation.
    void
    scramble(int[] indexes)
    Randomly shuffles a non-contiguous set of permutation elements.
    void
    scramble(int[] indexes, RandomGenerator r)
    Randomly shuffles a non-contiguous set of permutation elements.
    void
    scramble(int i, int j)
    Randomly shuffles a segment.
    void
    scramble(int i, int j, RandomGenerator r)
    Randomly shuffles a segment.
    void
    scramble(RandomGenerator r)
    Randomly shuffles the permutation.
    void
    scramble(RandomGenerator r, boolean guaranteeDifferent)
    Randomly shuffles the permutation.
    void
    set(int[] p)
    Changes the state of this permutation to be identical to the elements of an array.
    void
    swap(int i, int j)
    Swaps 2 integers in the permutation.
    void
    swapBlocks(int a, int b, int i, int j)
    Swaps 2 non-overlapping blocks, where a block is a subsequence.
    int[]
    toArray()
    Generates an array of int values from the interval [0, n) in the same order that they occur in this Permutation.
    int[]
    toArray(int[] array)
    Generates an array of int values from the interval [0, n) in the same order that they occur in this Permutation.
    BigInteger
    toBigInteger()
    Generates a unique integer representing the permutation.
    int
    toInteger()
    Generates a unique integer representing the permutation.
    String
    toString()
    Creates a String representing the permutation.

    Methods inherited from class java.lang.Object

    clone, finalize, getClass, notify, notifyAll, wait, wait, wait

    Methods inherited from interface java.lang.Iterable

    forEach, spliterator

  • Constructor Details

    • Permutation

      public Permutation(int n)
      Initializes a random permutation of n integers. Uses ThreadLocalRandom as the source of efficient random number generation.
      Parameters:
      n - the length of the permutation

    • Permutation

      public Permutation(int n, RandomGenerator r)
      Initializes a random permutation of n integers.
      Parameters:
      n - the length of the permutation
      r - A source of randomness.

    • Permutation

      public Permutation(int n, int value)
      Initializes a specific permutation from an integer in mixed radix form representing the chosen permutation. See the toInteger() method which can be used to generate this value for a given permutation. The n! permutations of the integers from 0 to n-1 are mapped to the integers from 0..(n!-1). Runtime of this constructor is O(n^2).
      Parameters:
      n - The length of the permutation.
      value - The integer value of the permutation in the interval: 0..(n!-1).

    • Permutation

      public Permutation(int n, BigInteger value)
      Initializes a specific permutation from an integer in mixed radix form representing the chosen permutation. See the toInteger() method which can be used to generate this value for a given permutation. The n! permutations of the integers from 0 to n-1 are mapped to the integers from 0..(n!-1). Runtime of this constructor is O(n^2).

      Even with the operations on BigInteger objects, the runtime is O(n^2). It performs O(n^2) operations on primitive values. It performs only O(n) divisions on BigInteger objects. It can be shown that the amortized cost of all of those divisions is bounded by the most costly division (each division involves progressively smaller numbers). The largest number involved in a division is the parameter value, which can be at most n!. The number n! consists of O(log((n-1)!)) = O(n log n) digits. Java's BigInteger division method currently implements the Burnikel-Ziegler algorithm, using the Toom–Cook multiplication algorithm. Dividing m-digit numbers with this combination has a runtime of O(m^1.465 log(m)). Substituting the number of digits for m, we have: O(n^1.465 log(n)^2.465). The cost of all of the divisions is thus less asymptotically than the cost of the primitive operations: O(n^2).

      Parameters:
      n - The length of the permutation.
      value - The integer value of the permutation in the interval: 0..(n!-1).

    • Permutation

      public Permutation(int[] p)
      Initializes a permutation of n integers to be identical to the elements of an array.
      Parameters:
      p - An array of integers. Each of the integers in the interval [0, p.length) must occur exactly one time each.
      Throws:
      IllegalArgumentException - if p either contains duplicates, or contains any negative elements, or contains any elements equal or greater than p.length.

    • Permutation

      public Permutation(Permutation p)
      Initializes a permutation of n integers to be identical to a given permutation.
      Parameters:
      p - the given permutation.

    • Permutation

      public Permutation(Permutation p, int length)
      Initializes a permutation of the integers in the interval [0, length) based on their relative order in a permutation p. If length is greater than or equal to p.length, then this constructor generates a copy of p. If length is less than p.length, then the new permutation contains the integers, 0, 1, 2, ..., (length - 1), in the order that those elements appear in p. For example, if p is the permutation [ 5, 3, 7, 2, 6, 1, 0, 8, 4] and if length is 4, this constructor will generate the permutation [3, 2, 1, 0] since 3 appears prior to 2, 2 appears prior to 1, and 1 appears prior to 0 in permutation p.
      Parameters:
      p - the source permutation.
      length - size of new permutation

  • Method Details

    • apply

      public void apply(PermutationUnaryOperator operator)
      Applies a custom unary operator on a Permutation object.
      Parameters:
      operator - A unary Permutation operator

    • apply

      public void apply(PermutationFullUnaryOperator operator)
      Applies a custom unary operator on a Permutation object.
      Parameters:
      operator - A unary Permutation operator

    • apply

      public void apply(PermutationBinaryOperator operator, Permutation other)
      Applies a custom binary operator on a pair of Permutation objects. The raw int array belonging to this is passed as the first array to operator.apply() and the raw int array belonging to other is passed as the second.
      Parameters:
      operator - A binary Permutation operator
      other - The other Permutation

    • apply

      public void apply(PermutationFullBinaryOperator operator, Permutation other)
      Applies a custom binary operator on a pair of Permutation objects. The raw int array belonging to this is passed as the first array to operator.apply() and the raw int array belonging to other is passed as the second, and this and other are passed as p1 and p2, respectively.
      Parameters:
      operator - A binary Permutation operator
      other - The other Permutation

    • applyThenValidate

      public void applyThenValidate(PermutationUnaryOperator operator)
      Applies a custom unary operator on a Permutation object, and then validates the state of the Permutation.
      Parameters:
      operator - A unary Permutation operator
      Throws:
      IllegalPermutationStateException - if the operator produced an illegal Permutation, in which case all subsequent method calls upon that Permutation may be unpredictable

    • applyThenValidate

      public void applyThenValidate(PermutationFullUnaryOperator operator)
      Applies a custom unary operator on a Permutation object, and then validates the state of the Permutation.
      Parameters:
      operator - A unary Permutation operator
      Throws:
      IllegalPermutationStateException - if the operator produced an illegal Permutation, in which case all subsequent method calls upon that Permutation may be unpredictable

    • applyThenValidate

      public void applyThenValidate(PermutationBinaryOperator operator, Permutation other)
      Applies a custom binary operator on a pair of Permutation objects, and then validates the state of the Permutation. The raw int array belonging to this is passed as the first array to operator.apply() and the raw int array belonging to other is passed as the second.
      Parameters:
      operator - A binary Permutation operator
      other - The other Permutation
      Throws:
      IllegalPermutationStateException - if the operator produced an illegal Permutation, in which case all subsequent method calls upon that Permutation may be unpredictable, and the illegal state may be either or both of the Permutation objects

    • applyThenValidate

      public void applyThenValidate(PermutationFullBinaryOperator operator, Permutation other)
      Applies a custom binary operator on a pair of Permutation objects, and then validates the state of the Permutation. The raw int array belonging to this is passed as the first array to operator.apply() and the raw int array belonging to other is passed as the second, and this and other are passed as p1 and p2, respectively.
      Parameters:
      operator - A binary Permutation operator
      other - The other Permutation
      Throws:
      IllegalPermutationStateException - if the operator produced an illegal Permutation, in which case all subsequent method calls upon that Permutation may be unpredictable, and the illegal state may be either or both of the Permutation objects

    • copy

      public Permutation copy()
      Creates an identical copy of this object.
      Specified by:
      copy in interface Copyable<Permutation>
      Returns:
      an identical copy of this object

    • toInteger

      public int toInteger()
      Generates a unique integer representing the permutation. Maps the permutations of the integers, 0..(N-1), to the integers, 0..(N!-1), using a mixed radix representation. This method is only supported for permutations of length 12 or less. Runtime of this method is O(N^2).
      Returns:
      a mixed radix representation of the permutation
      Throws:
      UnsupportedOperationException - when permutation length is greater than 12.

    • toBigInteger

      public BigInteger toBigInteger()
      Generates a unique integer representing the permutation. Maps the permutations of the integers, 0..(N-1), to the integers, 0..(N!-1), using a mixed radix representation.

      Even with the use of BigInteger objects, the runtime of this method is O(N^2). Specifically, it performs O(N^2) operations on primitives. And the sequence of operations on BigIntegers costs no more than the cost to compute N! using BigInteger objects, whose runtime bounded by that of the last multiplication of N * (N-1)! The number (N-1)! consists of O(log((N-1)!)) = O(N log N) digits. Java's BigInteger.multiply currently implements the Toom–Cook algorithm, which has a runtime for M-digit numbers of O(M^1.465). Thus, the cost of all of the BigInteger operations is O(N^1.465 log(N)^1.465). Therefore, the runtime is dominated by the cost of the primitive operations: O(N^2).

      Returns:
      a mixed radix representation of the permutation

    • getInverse

      public int[] getInverse()
      Computes the inverse of the permutation.
      Returns:
      The inverse of the permutation, such that for all i, if pi(i) = j, then inv(j) = i

    • getInversePermutation

      public Permutation getInversePermutation()
      Computes a Permutation that is the inverse of this Permutation. Specifically, this.get(i) == j iff inverse.get(j) == i.
      Returns:
      The inverse of the permutation, such that for all i, this.get(i) == j iff inverse.get(j) == i.

    • invert

      public void invert()
      Inverts the Permutation, such that if p1 is the Permutation immediately prior to the call to invert, and if p2 is the Permutation immediately after the call to invert, then p1.get(i) == j iff p2.get(j) == i, for all i, j.

    • scramble

      public void scramble()
      Randomly shuffles the permutation. Uses ThreadLocalRandom as the source of efficient random number generation.

    • scramble

      public void scramble(RandomGenerator r)
      Randomly shuffles the permutation.
      Parameters:
      r - a source of randomness.

    • scramble

      public void scramble(boolean guaranteeDifferent)
      Randomly shuffles the permutation. Uses ThreadLocalRandom as the source of efficient random number generation.
      Parameters:
      guaranteeDifferent - if true and if permutation length is at least 2, then method guarantees that the result is a different permutation than it was originally.

    • scramble

      public void scramble(RandomGenerator r, boolean guaranteeDifferent)
      Randomly shuffles the permutation.
      Parameters:
      r - a source of randomness.
      guaranteeDifferent - if true and if permutation length is at least 2, then method guarantees that the result is a different permutation than it was originally.

    • scramble

      public void scramble(int i, int j)
      Randomly shuffles a segment. Uses ThreadLocalRandom as the source of efficient random number generation. As long as two different indexes are passed to this method, it is guaranteed to change the permutation.
      Parameters:
      i - endpoint of the segment (precondition: 0 ≤ i < length())
      j - endpoint of the segment (precondition: 0 ≤ j < length())
      Throws:
      ArrayIndexOutOfBoundsException - if either i or j are negative, or if either i or j are greater than or equal to length()

    • scramble

      public void scramble(int i, int j, RandomGenerator r)
      Randomly shuffles a segment. As long as two different indexes are passed to this method, it is guaranteed to change the permutation.
      Parameters:
      i - endpoint of the segment (precondition: 0 ≤ i < length())
      j - endpoint of the segment (precondition: 0 ≤ j < length())
      r - source of randomness
      Throws:
      ArrayIndexOutOfBoundsException - if either i or j are negative, or if either i or j are greater than or equal to length()

    • scramble

      public void scramble(int[] indexes, RandomGenerator r)
      Randomly shuffles a non-contiguous set of permutation elements. As long as there are at least 2 different indexes passed to this method, it is guaranteed to change the Permutation.
      Parameters:
      indexes - An array of indexes into the permutation. This method assumes that the indexes are valid indexes into the permutation. That is, it assumes that 0 ≤ indexes[i] < this.length().
      r - source of randomness
      Throws:
      ArrayIndexOutOfBoundsException - if any of the indexes[i] are negative or greater than or equal to this.length().

    • scramble

      public void scramble(int[] indexes)
      Randomly shuffles a non-contiguous set of permutation elements. As long as there are at least 2 different indexes passed to this method, it is guaranteed to change the Permutation.
      Parameters:
      indexes - An array of indexes into the permutation. This method assumes that the indexes are valid indexes into the permutation. That is, it assumes that 0 ≤ indexes[i] < this.length().
      Throws:
      ArrayIndexOutOfBoundsException - if any of the indexes[i] are negative or greater than or equal to this.length().

    • get

      public int get(int i)
      Retrieves the i-th integer of the permutation.
      Parameters:
      i - the index of the integer to retrieve. (precondition: 0 ≤ i < length())
      Returns:
      the integer in the i-th position.
      Throws:
      ArrayIndexOutOfBoundsException - if i is negative, or if i is greater than or equal to length()

    • get

      public int[] get(int i, int j)
      Retrieves a range of elements from the permutation.
      Parameters:
      i - The starting index.
      j - The ending index (inclusive).
      Returns:
      An array containing the permutation elements from positions i through j, inclusive.
      Throws:
      IllegalArgumentException - if j < i
      IndexOutOfBoundsException - if i is negative, or j ≥ Permutation.length()

    • get

      public int[] get(int i, int j, int[] array)
      Retrieves a range of elements from the permutation.
      Parameters:
      i - The starting index.
      j - The ending index (inclusive).
      array - An array to hold the result. If the array is null or if its length is not equal to the number of retrieved elements, then a new array is constructed.
      Returns:
      The array containing the permutation elements from positions i through j, inclusive.
      Throws:
      IllegalArgumentException - if j < i
      IndexOutOfBoundsException - if i is negative, or j ≥ Permutation.length()

    • toArray

      public int[] toArray()
      Generates an array of int values from the interval [0, n) in the same order that they occur in this Permutation. The array that is returned is independent of the object state (i.e., changes to its contents will not affect the Permutation).
      Returns:
      an int array containing the Permutation elements in the same order that they appear in the Permutation.

    • toArray

      public int[] toArray(int[] array)
      Generates an array of int values from the interval [0, n) in the same order that they occur in this Permutation. The array that is returned is independent of the object state (i.e., changes to its contents will not affect the Permutation).
      Parameters:
      array - An array to hold the result. If array is null or if array.length is not equal to the length of the permutation, then this method will construct a new array for the result.
      Returns:
      an int array containing the Permutation elements in the same order that they appear in the Permutation.

    • length

      public int length()
      Retrieves the length of the permutation.
      Returns:
      length of the permutation

    • swap

      public void swap(int i, int j)
      Swaps 2 integers in the permutation.
      Parameters:
      i - position of first to swap (precondition: 0 ≤ i < length() ∧ i != j)
      j - the position of the second to swap (precondition: 0 ≤ j < length() ∧ i != j)
      Throws:
      ArrayIndexOutOfBoundsException - if either i or j are negative, or if either i or j are greater than or equal to length()

    • cycle

      public void cycle(int[] indexes)
      Creates a permutation cycle from a sequence of permutation indexes. Let p1 be the permutation before the call to cycle, and let p2 be the permutation after the call to cycle. For i from 1 to indexes.length - 1, p2.get(indexes[i-1])==p1.get(indexes[i]); and p2.get(indexes[indexes.length - 1])==p1.get(indexes[0]). Note that passing an array containing two indexes to this method is equivalent to a swap(int, int), and passing fewer than 2 indexes does nothing.
      Parameters:
      indexes - an array of indexes into the permutation.
      Throws:
      ArrayIndexOutOfBoundsException - if there exists any indexes[i] ≥ this.length() or indexes[i] < 0.

    • swapBlocks

      public void swapBlocks(int a, int b, int i, int j)
      Swaps 2 non-overlapping blocks, where a block is a subsequence.
      Parameters:
      a - Starting index of first block.
      b - Ending index, inclusive, of first block.
      i - Starting index of second block.
      j - Ending index, inclusive, of second block.
      Throws:
      IllegalArgumentException - if the following constraint is violated: 0 ≤ a ≤ b < i ≤ j < length().

    • reverse

      public void reverse()
      Reverses the order of the elements in the permutation.

    • reverse

      public void reverse(int i, int j)
      Reverses the order of the elements of a subrange of the permutation.
      Parameters:
      i - position of first index (precondition: 0 ≤ i < length() ∧ i != j)
      j - the position of the second index (precondition: 0 ≤ j < length() ∧ i != j)
      Throws:
      ArrayIndexOutOfBoundsException - if either i or j are negative, or if either i or j are greater than or equal to length()

    • removeAndInsert

      public void removeAndInsert(int i, int j)
      Removes integer from one position and then inserts it into a a new position shifting the rest of the permutation as necessary.
      Parameters:
      i - position of integer to remove and insert (precondition: 0 ≤ i < length())
      j - the position of the insertion point (precondition: 0 ≤ j < length())
      Throws:
      ArrayIndexOutOfBoundsException - if either i or j are negative, or if either i or j are greater than or equal to length()

    • rotate

      public void rotate(int numPositions)
      Circular rotation of permutation (to the left).
      Parameters:
      numPositions - Number of positions to rotate.

    • removeAndInsert

      public void removeAndInsert(int i, int size, int j)
      Removes a sub-array of integers from one position and then inserts it into a a new position shifting the rest of the permutation as necessary.
      Parameters:
      i - position of first integer in sub-array to remove and insert (precondition: 0 ≤ i < length())
      size - the length of the sub-array (precondition: size + i < length() and size + j - 1 < length())
      j - the position of the insertion point (precondition: 0 ≤ j < length())
      Throws:
      ArrayIndexOutOfBoundsException - if either i or j are negative, or if either i or j are greater than or equal to length().

    • set

      public void set(int[] p)
      Changes the state of this permutation to be identical to the elements of an array.
      Parameters:
      p - An array of integers. Each of the integers in the interval [0, p.length) must occur exactly one time each.
      Throws:
      IllegalArgumentException - if p either contains duplicates, or contains any negative elements, or contains any elements equal or greater than p.length.

    • iterator

      public Iterator<Permutation> iterator()
      Returns an Iterator over all Permutations the length of this Permutation. Iteration begins at this Permutation. This Iterator does not iterate over the integers within the Permutation. If you do need to iterate over all permutations of a given length, then this method is much more efficient than using the Permutation(int,int) constructor repeatedly incrementing the value passed for the second parameter.
      Specified by:
      iterator in interface Iterable<Permutation>
      Returns:
      an Iterator

    • toString

      public String toString()
      Creates a String representing the permutation.
      Overrides:
      toString in class Object
      Returns:
      a space separated sequence of the permutation's elements

    • equals

      public boolean equals(Object other)
      Equality test: Two permutations are equal if they are of the same length and contain the same elements in the same order.
      Overrides:
      equals in class Object
      Parameters:
      other - the permutation to which to compare
      Returns:
      true if this is equal to other, and false otherwise

    • hashCode

      public int hashCode()
      Uses Java's Arrays class's method for generating a hashCode from an array of ints.
      Overrides:
      hashCode in class Object
      Returns:
      a hashCode for the permutation