Package eu.bandm.tools.util.uni

Class Permutation.CanonicalForm

java.lang.Object

eu.bandm.tools.util.uni.Permutation.CanonicalForm

All Implemented Interfaces:

Serializable

Enclosing class:

Permutation

public static class Permutation.CanonicalForm
extends Object
implements Serializable

Canonical form of a permutation.

The canonical form consists of a sequence of sequences of integers:

1. Each subsequence specifies a cycle, starting with the highest member.
2. The outer sequence is ordered ascendingly by starting members.
3. Trivial cycles that contain only one element are omitted.

These rules ensure that the canonical form is finite and uniquely determined.

The permutation can be reconstructed from the canonical form; the following expression is equivalent to p:

   p.canonicalForm().stream()
       .map(Permutation::cycle)
       .reduce(Permutation.identity(), Permutation::compose)
 

Several algebraic operations on permutations are algorithmically easier on their canonical forms. Therefore canonical forms may be computed internally as a preliminary step.

See Also:

• Permutation.canonicalForm
• Permutation.of(CanonicalForm)
• Permutation.cycle(int...)
• Serialized Form

Constructor Summary

Constructors

Constructor	Description
CanonicalForm(int[][] cycles)	Creates a new instance.

Method Summary

Modifier and Type	Method	Description
boolean	equals(Object o)
int	hashCode()
void	shuffle(int[] seq)	Permutes the elements of a sequence according to this canonical form.
void	shuffle(Object[] seq)	Permutes the elements of a sequence according to this canonical form.
<E> void	shuffle(List<E> seq)	Permutes the elements of a sequence according to this canonical form.
Optional<Permutation.CanonicalForm>	sqrt()	Finds some canonical form that composed with itself is equivalent to this canonical form.
Stream<int[]>	stream()	Returns a stream of integer sequences representing the cycles of this canonical form.
String	toString()

Methods inherited from class java.lang.Object

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

Constructor Details

CanonicalForm

CanonicalForm(int[][] cycles)

Creates a new instance. Do not call this constructor directly!

Parameters:

cycles - the ordered sequence of nontrivial cycles

Method Details

equals

public boolean equals(Object o)

Overrides:

equals in class Object

hashCode

public int hashCode()

Overrides:

hashCode in class Object

toString

public String toString()

Overrides:

toString in class Object

stream

public Stream<int[]> stream()

Returns a stream of integer sequences representing the cycles of this canonical form.

The elements of the stream are copies of the internal data structures of this object; subsequent modifications by the caller have no effect on the internal state of the canonical form.

Returns:

a stream of cycles

shuffle

public void shuffle(Object[] seq)

Permutes the elements of a sequence according to this canonical form.

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

Parameters:

seq - the sequence to permute

Throws:

NullPointerException - if seq is null

See Also:

• Permutation.shuffle(Object[])

shuffle

public void shuffle(int[] seq)

Permutes the elements of a sequence according to this canonical form.

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

Parameters:

seq - the sequence to permute

Throws:

NullPointerException - if seq is null

See Also:

• Permutation.shuffle(int[])

shuffle

public <E> void shuffle(List<E> seq)

Permutes the elements of a sequence according to this canonical form.

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

Type Parameters:

E - the element type

Parameters:

seq - the sequence to permute

Throws:

NullPointerException - if seq is null

See Also:

• Permutation.shuffle(List)

sqrt

public Optional<Permutation.CanonicalForm> sqrt()

Finds some canonical form that composed with itself is equivalent to this canonical form.

The implemented algorithm is stable; for equivalent canonical forms, 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 canonical form that composed with itself is equivalent to this canonical form; or Optional.empty() if none exists.