Package eu.bandm.tools.util.uni

Class Permutation

java.lang.Object
eu.bandm.tools.util.uni.Permutation
All Implemented Interfaces:
Serializable
public class Permutation extends Object implements Serializable
Unsized zero-indexed finite permutations.

A permutation is a one-to-one (bijective) mapping of a set to itself. For finite sets, the elements are not represented concretely, but by an abstract numbering. This implementation uses the primitive type int for numbers.

Zero/One Indexing

Objects of this class generally represent permutations that are zero-indexed: A finite set of n elements is represented by the integers 0, …, n−1. This convention is very prominent in computer science; but much less so in mathematics, where one-indexing is the norm.

In order to have a finite set of n elements represented by the integers 1, …, n instead, use permutations where 0 is mapped to 0. This property is preserved by all the usual algebraic operations on permutations (unless index 0 is passed explicitly), and can be checked with the isOneBased() method. Use shift(int) to convert between the two views.

Size

Objects of this class encode one-to-one mappings on integers. The size of the set they are applied to is not part of their defining properties. Instead, the following rules apply (and are enforced by the get(int) method):

  • A permutation is always undefined on the negative integers.
  • A permutation is always defined on the non-negative integers. Their definition, however, may only mention a bounded subset of numbers. For all numbers that exceed the bound, permutations act as the identical function, mapping each such number to itself. Compare the behavior of class BitSet.

Immutability

Like all mathematical entities, permutations are represented accurately by immutable data structures. Instead of modifying an existing permutation object after its creation, a new derived one is created using a variety of algebraic operations.

Hence objects of this class are always created by means of static factory methods, and interacted with solely by calling stateless (getter) methods.

See Also:

  • Nested Class Summary

    Nested Classes
    Modifier and Type
    Class
    Description
    static class 
    Permutation.CanonicalForm
    Canonical form of a permutation.

  • Constructor Summary

    Constructors
    Constructor
    Description
    Permutation(int[] elems, boolean even)
    Creates a new instance.

  • Method Summary

    Modifier and Type
    Method
    Description
    IntUnaryOperator
    action()
    Returns an operator that maps every index to the value assigned by this permutation.
    Permutation
    andThen(Permutation other)
    Returns a permutation that applies the mapping of this permutation before that of a given other permutation.
    Permutation.CanonicalForm
    canonicalForm()
    Represents this permutation in canonical form.
    Permutation
    compose(Permutation other)
    Returns a permutation that applies the mapping of this permutation after that of a given other permutation.
    static Permutation
    cycle(int... members)
    Returns a permutation that rotates the given positions cyclically.
    boolean
    equals(Object o)
    Checks whether some object is equal to this permutation.
    int
    get(int index)
    Returns the value assigned to the given index by this permutation.
    int
    hashCode()
    Computes a hash code for this permutation.
    (package private) boolean
    hasParity()
    Checks whether this permutation has the correct parity bit.
    static Permutation
    identity()
    Returns the identity permutation.
    Permutation
    inverse()
    Returns a permutation that inverts the mapping of this permutation.
    boolean
    isEven()
    Checks whether this permutation is of even parity.
    (package private) boolean
    isInjective()
    Checks whether all entries of this permutation are unique.
    (package private) boolean
    isInRange()
    Checks whether all entries of this permutation are in the valid range.
    (package private) boolean
    isMinimal()
    Checks whether all entries of this permutation are necessary.
    boolean
    isOneBased()
    Checks whether this permutation can represent a set with one-based indexing.
    (package private) boolean
    isValid()
    Checks whether the representation of this permutation is valid.
    static Permutation
    mirror(int from, int to)
    Returns a permutation that mirrors the positions in a given interval.
    static Permutation
    of(Permutation.CanonicalForm canonicalForm)
    Creates a permutation from its canonical form.
    Permutation
    power(long exponent)
    Returns a repeated composition of this permutation with itself.
    static Permutation
    rotate(int from, int to)
    Returns a permutation that rotates the positions in a given interval one step up.
    Optional<Permutation>
    shift(int offset)
    Returns a copy of this permutation where all entries are shifted by a given offset.
    Optional<Permutation>
    shiftDown(int offset)
    Returns a copy of this permutation where all entries are shifted downwards by a given offset.
    Permutation
    shiftUp(int offset)
    Returns a copy of this permutation where all entries are shifted upwards by a given offset.
    void
    shuffle(int[] seq)
    Permutes the elements of a sequence according to this permutation.
    void
    shuffle(Object[] seq)
    Permutes the elements of a sequence according to this permutation.
    void
    shuffle(List<?> seq)
    Permutes the elements of a sequence according to this permutation.
    int
    sign()
    Returns the parity sign of this permutation.
    static Permutation
    sorting(int[] seq)
    Returns the permutation that sorts the given sequence in ascending numerical ordering.
    static <E extends Comparable<? super E>>
    Permutation
    sorting(E[] seq)
    Returns the permutation that sorts the given sequence in natural ordering.
    static <E> Permutation
    sorting(E[] seq, Comparator<? super E> comp)
    Returns the permutation that sorts the given sequence in the given ordering.
    static <E extends Comparable<? super E>>
    Permutation
    sorting(List<? extends E> seq)
    Returns the permutation that sorts the given sequence in natural ordering.
    static <E> Permutation
    sorting(List<? extends E> seq, Comparator<? super E> comp)
    Returns the permutation that sorts the given sequence in the given ordering.
    Optional<Permutation>
    sqrt()
    Finds some permutation that composed with itself is equivalent to this permutation.
    String
    substitute(String text)
    Substitute each Unicode code point in the given string according to this permutation.
    static Permutation
    swap(int a, int b)
    Returns a permutation that swaps two positions.
    String
    toString()
    Returns a human-readable presentation of this permutation.
    static Permutation
    unsorting(int... seq)
    Returns the permutation that reproduces the given sequence from its sorted elements.

    Methods inherited from class java.lang.Object

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

  • Constructor Details

    • Permutation

      Permutation(int[] elems, boolean even)
      Creates a new instance. Do not call this constructor directly!
      Parameters:
      elems - the minimal mapping
      even - the parity
      Throws:
      NullPointerException - if elems is null

  • Method Details

    • identity

      public static Permutation identity()
      Returns the identity permutation.
      Returns:
      the permutation that assigns each index to itself

    • get

      public int get(int index)
      Returns the value assigned to the given index by this permutation.
      Parameters:
      index - the nonnegative index
      Returns:
      the value mapped to the given index
      Throws:
      IllegalArgumentException - if index < 0

    • action

      public IntUnaryOperator action()
      Returns an operator that maps every index to the value assigned by this permutation.
      Returns:
      an operator that maps every i to this.get(i)
      See Also:

    • isEven

      public boolean isEven()
      Checks whether this permutation is of even parity.

      A permutation is of even (odd) parity, if and only if it can be decomposed into an even (odd) number of proper swaps, respectively.

      Returns:
      true if this permutation is of even parity; false if it is of odd parity
      See Also:

    • sign

      public int sign()
      Returns the parity sign of this permutation.
      Returns:
      1 if this permutation is of even parity; -1 if it is of odd parity
      See Also:

    • isOneBased

      public boolean isOneBased()
      Checks whether this permutation can represent a set with one-based indexing.
      Returns:
      true if 0 is assigned to 0; false otherwise

    • isInRange

      boolean isInRange()
      Checks whether all entries of this permutation are in the valid range.
      Returns:
      true if all entries are also valid indices; false otherwise

    • isInjective

      boolean isInjective()
      Checks whether all entries of this permutation are unique.
      Returns:
      false if there are two entries with identical values; true otherwise

    • isMinimal

      boolean isMinimal()
      Checks whether all entries of this permutation are necessary.
      Returns:
      false if equivalent behavior can be specified by a shorter mapping array; true otherwise

    • hasParity

      boolean hasParity()
      Checks whether this permutation has the correct parity bit.

      This method uses a quadratic algorithm, and should not be called too often.

      Returns:
      true if even is equal to the computed parity; false otherwise

    • isValid

      boolean isValid()
      Checks whether the representation of this permutation is valid.

      A permutations created by the static factory methods in this class are valid by construction. Hence this method should only be called for the purpose of testing extensions.

      Returns:
      true if all invariants are satisfied; false otherwise

    • compose

      public Permutation compose(Permutation other)
      Returns a permutation that applies the mapping of this permutation after that of a given other permutation.
      p.compose(q).get(i) == p.get(q.get(i))
      Parameters:
      other - the permutation to apply before this one
      Returns:
      a permutation that applies this after other

    • andThen

      public Permutation andThen(Permutation other)
      Returns a permutation that applies the mapping of this permutation before that of a given other permutation.
      p.andThen(q).get(i) == q.get(p.get(i))
      Parameters:
      other - the permutation to apply after this one
      Returns:
      a permutation that applies this before other

    • inverse

      public Permutation inverse()
      Returns a permutation that inverts the mapping of this permutation.
      p.inverse().get(p.get(i)) == i, as well as p.get(p.inverse().get(i)) == i
      Returns:
      the inverse permutation

    • equals

      public boolean equals(Object o)
      Checks whether some object is equal to this permutation.
      Overrides:
      equals in class Object

    • hashCode

      public int hashCode()
      Computes a hash code for this permutation.
      Overrides:
      hashCode in class Object

    • toString

      public String toString()
      Returns a human-readable presentation of this permutation.
      Overrides:
      toString in class Object
      See Also:
      • canonicalForm

    • swap

      public static Permutation swap(int a, int b)
      Returns a permutation that swaps two positions.

      The resulting permutation behaves as follows (and like the identity elsewhere):

      swap(a, b).get(a) == b, and swap(a, b).get(b) == a

      It is implied that the result is the identity permutation if a == b.

      Parameters:
      a - the position to swap with b
      b - the position to swap with a
      Returns:
      a permutation that assigns value a to index b and vice versa, and is the identity otherwise
      Throws:
      IllegalArgumentException - if a < 0 or b < 0

    • rotate

      public static Permutation rotate(int from, int to)
      Returns a permutation that rotates the positions in a given interval one step up.

      The resulting permutation behaves as follows (and like the identity elsewhere):

      p.rotate(from, to).get(i) == i + 1 if i >= from && i < to, and p.rotate(from, to).get(to) == from

      It is implied that the result is the identity permutation if from >= to.

      To rotate an arbitrary number of steps up or down, use power(long) on the result.

      Parameters:
      from - the lower end of the position interval to rotate, inclusively
      to - the upper end of the position interval to rotate, inclusively
      Returns:
      a permutation that rotates the positions in the interval from–to one step up
      See Also:

    • mirror

      public static Permutation mirror(int from, int to)
      Returns a permutation that mirrors the positions in a given interval.

      The resulting permutation behaves as follows (and like the identity elsewhere):

      p.mirror(from, to).get(i) == from + to - i if i >= from && i <= to

      It is implied that the result is the identity permutation if from >= to.

      Parameters:
      from - the lower end of the position interval to mirror, inclusively
      to - the upper end of the position interval to mirror, inclusively
      Returns:
      a permutation that mirrors the positions in the interval from–to

    • cycle

      public static Permutation cycle(int... members)
      Returns a permutation that rotates the given positions cyclically.

      The resulting permutation behaves as follows (and like the identity elsewhere):

      p.cycle(members).get(members[i]) == members[(i + 1) % members.length]

      It is implied that the result is the identity permutation if members.length <= 1.

      Parameters:
      members - an injective sequence of cycle members
      Returns:
      a permutation that rotates the given positions cyclically
      Throws:
      NullPointerException - if members is null
      IllegalArgumentException - if members contains a negative value, or contains the same value more than once

    • canonicalForm

      public Permutation.CanonicalForm canonicalForm()
      Represents this permutation in canonical form.

      The result is stable, and may be cached to speed up subsequent calls of this method.

      Returns:
      a representation of this permutation in canonical form
      See Also:

    • of

      public static Permutation of(Permutation.CanonicalForm canonicalForm)
      Creates a permutation from its canonical form.

      Behavior is undefined if the given array does not represent a canonical form.

      Parameters:
      canonicalForm - a canonical form
      Returns:
      a permutation with the given canonical form
      See Also:
      • canonicalForm

    • power

      public Permutation power(long exponent)
      Returns a repeated composition of this permutation with itself.

      If the given number of repetitions is negative, inversion is implied.

      The number of algebraic operations on permutations invoked by this algorithm grows only logarithmically with the exponent; even very large powers are feasible to compute.

      Parameters:
      exponent - the number of repetitions
      Returns:
      the exponent-fold composition of this permutation with itself

    • shuffle

      public void shuffle(Object[] seq)
      Permutes the elements of a sequence according to this permutation.

      The element at each index i is moved to index get(i).

      This method implements a two-phase algorithm:

      1. The first phase calculates the canonical form of this permutation.
      2. The second phase moves elements in cycles, using a single temporary variable.
      Parameters:
      seq - the sequence to permute
      Throws:
      NullPointerException - if seq is null
      See Also:

    • shuffle

      public void shuffle(int[] seq)
      Permutes the elements of a sequence according to this permutation.

      The element at each index i is moved to index get(i).

      This method implements a two-phase algorithm:

      1. The first phase calculates the canonical form of this permutation.
      2. The second phase moves elements in cycles, using a single temporary variable.
      Parameters:
      seq - the sequence to permute
      Throws:
      NullPointerException - if seq is null
      See Also:

    • shuffle

      public void shuffle(List<?> seq)
      Permutes the elements of a sequence according to this permutation.

      The element at each index i is moved to index get(i).

      This method implements a two-phase algorithm:

      1. The first phase calculates the canonical form of this permutation.
      2. The second phase moves elements in cycles, using a single temporary variable.
      Parameters:
      seq - the sequence to permute
      Throws:
      NullPointerException - if seq is null
      See Also:

    • sqrt

      public Optional<Permutation> sqrt()
      Finds some permutation that composed with itself is equivalent to this permutation.

      The implemented algorithm is stable; for equivalent permutations, equivalent results are obtained always. It is also complete; if there are any solutions, one will be found. It is not unique; if there are several solutions, only a single, arbitrary one is found.

      Returns:
      some permutation that composed with itself is equivalent to this permutation; or Optional.empty() if none exists.

    • shift

      public Optional<Permutation> shift(int offset)
      Returns a copy of this permutation where all entries are shifted by a given offset.

      If this construction succeeds, the result behaves as follows:

      p.shift(k).get(i) = p.get(i - k) + k, if i and i-k are both nonnegative

      The effect of shifting depends on the sign of the offset:

      • If offset is positive, then all existing entries are shifted upwards, padded with identical entries at the lower end.
      • If offset is zero, then the result is equivalent to this permutation.
      • If offset is negative, then all existing entries are shifted downwards. Entries below the offset threshold are deleted. If any of the remaining entries is left dangling (points to a deleted one), the result would be inconsistent; the construction fails in this case.
      Parameters:
      offset - the offset
      Returns:
      a copy of this permutation shifted by offset; or Optional.empty() if offset is negative and the result would be inconsistent
      See Also:

    • shiftUp

      public Permutation shiftUp(int offset)
      Returns a copy of this permutation where all entries are shifted upwards by a given offset.

      If this construction succeeds, the result behaves as follows:

      p.shift(k).get(i) = p.get(i - k) + k, if i and i-k are both nonnegative
      Parameters:
      offset - the nonnegative offset
      Returns:
      a copy of this permutation shifted upwards by offset
      Throws:
      IllegalArgumentException - if offset < 0
      See Also:

    • shiftDown

      public Optional<Permutation> shiftDown(int offset)
      Returns a copy of this permutation where all entries are shifted downwards by a given offset.

      If this construction succeeds, the result behaves as follows:

      p.shift(k).get(i) = p.get(i - k) + k, if i and i-k are both nonnegative

      If the right-hand side is found be negative in a valid case, the resulting permutation would be inconsistent, and the construction fails.

      Parameters:
      offset - the nonnegative offset
      Returns:
      a copy of this permutation shifted downwards by offset; or Optional.empty() if the result would be inconsistent
      Throws:
      IllegalArgumentException - if offset < 0
      See Also:

    • sorting

      public static <E extends Comparable<? super E>> Permutation sorting(E[] seq)
      Returns the permutation that sorts the given sequence in natural ordering.
      sorting(s).shuffle(s) has the same effect as Arrays.sort(s).

      The result corresponds to a stable sorting algorithm; equal elements are never transposed. This also makes the result uniquely specified.

      Type Parameters:
      E - the type of sequence elements
      Parameters:
      seq - the sequence
      Returns:
      the permutation that sorts seq
      Throws:
      NullPointerException - if seq is or contains null

    • sorting

      public static <E> Permutation sorting(E[] seq, Comparator<? super E> comp)
      Returns the permutation that sorts the given sequence in the given ordering.
      sorting(c, s).shuffle(s) has the same effect as Arrays.sort(s, c).

      The result corresponds to a stable sorting algorithm; equal elements are never transposed. This also makes the result uniquely specified.

      Type Parameters:
      E - the type of sequence elements
      Parameters:
      seq - the sequence
      comp - the comparator that specifies the ordering
      Returns:
      the permutation that sorts seq according to comp
      Throws:
      NullPointerException - if comp is null, or if seq is or contains null

    • sorting

      public static Permutation sorting(int[] seq)
      Returns the permutation that sorts the given sequence in ascending numerical ordering.
      sorting(s).shuffle(s) has the same effect as Arrays.sort(s).

      The result corresponds to a stable sorting algorithm; equal elements are never transposed. This also makes the result uniquely specified.

      Parameters:
      seq - the sequence
      Returns:
      the permutation that sorts seq
      Throws:
      NullPointerException - if seq is or contains null
      See Also:

    • sorting

      public static <E extends Comparable<? super E>> Permutation sorting(List<? extends E> seq)
      Returns the permutation that sorts the given sequence in natural ordering.
      sorting(s).shuffle(s) has the same effect as Collections.sort(s).

      The result corresponds to a stable sorting algorithm; equal elements are never transposed. This also makes the result uniquely specified.

      Type Parameters:
      E - the type of sequence elements
      Parameters:
      seq - the sequence
      Returns:
      the permutation that sorts seq
      Throws:
      NullPointerException - if seq is or contains null

    • sorting

      public static <E> Permutation sorting(List<? extends E> seq, Comparator<? super E> comp)
      Returns the permutation that sorts the given sequence in the given ordering.
      sorting(c, s).shuffle(s) has the same effect as Collections.sort(s, c).

      The result corresponds to a stable sorting algorithm; equal elements are never transposed. This also makes the result uniquely specified.

      Type Parameters:
      E - the type of sequence elements
      Parameters:
      seq - the sequence
      comp - the comparator that specifies the ordering
      Returns:
      the permutation that sorts seq according to comp
      Throws:
      NullPointerException - if comp is null, or if seq is or contains null

    • unsorting

      public static Permutation unsorting(int... seq)
      Returns the permutation that reproduces the given sequence from its sorted elements.

      The following sequence of operations effectively restores the sequence seq to its original content: 

      
   final Permutation p = unsorting(seq);
   Arrays.sort(seq);
   p.shuffle(seq);

      This method is a convenient robust tool for notating a permutation ad-hoc. The given elements are not constrained in the way that permutation entries are: Negative values, non-contiguous range and duplicates are all allowed here. The hypothetical underlying sorting is by ascending numerical value.

      The result corresponds to a stable sorting algorithm; equal elements are never transposed. This also makes the result uniquely specified.

      If the given sequence literally specifies entries of a permutation, i.e., if its elements cover the range 0, …, n−1 without duplicates, then the result is that permutation. Conversely, if the given sequence is sorted in ascending numerical order, then the result is the identical permutation.

      Parameters:
      seq - a sequence of arbitrary integer values
      Returns:
      a permutation that reproduces seq from its sorted elements
      Throws:
      NullPointerException - if seq is null
      See Also:

    • substitute

      public String substitute(String text)
      Substitute each Unicode code point in the given string according to this permutation.
      p.substitute(s).codePoints() and s.codePoints().map(p::get) produce equivalent streams

      Note that there is no general simple index-based expression of this specification, since a code point that fits in a single char may be substituted for one that requires a surrogate pair, and/or vice versa.

      Parameters:
      text - a cleartext string
      Returns:
      the cyphertext resulting from substituting each code point using this.get
      Throws:
      NullPointerException - if text is null