 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 N1, inclusive. This class provides the functionality to generate random permutations, and to manipulate permutations in a variety of ways. See Also:
 Serialized Form


Nested Class Summary
Nested Classes Modifier and Type Class Description static class
Permutation.Mechanic
The Permutation.Mechanic class provides a means of adding applicationspecific operations on Permutations without the need to directly alter the Permutation class.

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, Random r)
Initializes a random permutation of n integers.Permutation(int n, SplittableRandom 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
All Methods Instance Methods Concrete Methods Modifier and Type Method Description 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 subarray 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 noncontiguous set of permutation elements.void
scramble(int[] indexes, Random r)
Randomly shuffles a noncontiguous set of permutation elements.void
scramble(int[] indexes, SplittableRandom r)
Randomly shuffles a noncontiguous set of permutation elements.void
scramble(int i, int j)
Randomly shuffles a segment.void
scramble(int i, int j, Random r)
Randomly shuffles a segment.void
scramble(int i, int j, SplittableRandom r)
Randomly shuffles a segment.void
scramble(Random r)
Randomly shuffles the permutation.void
scramble(Random r, boolean guaranteeDifferent)
Randomly shuffles the permutation.void
scramble(SplittableRandom r)
Randomly shuffles the permutation.void
scramble(SplittableRandom 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 nonoverlapping 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 Detail

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

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

Permutation
public Permutation(int n, Random r)
Initializes a random permutation of n integers. Parameters:
n
 the length of the permutationr
 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 n1 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 n1 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((n1)!)) = O(n log n) digits. Java's BigInteger division method currently implements the BurnikelZiegler algorithm, using the Toomâ€“Cook multiplication algorithm. Dividing mdigit 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 Detail

copy
public Permutation copy()
Creates an identical copy of this object. Specified by:
copy
in interfaceCopyable<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..(N1), 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..(N1), 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 * (N1)! The number (N1)! consists of O(log((N1)!)) = O(N log N) digits. Java's BigInteger.multiply currently implements the Toomâ€“Cook algorithm, which has a runtime for Mdigit 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 java.util.concurrent.ThreadLocalRandom as the source of efficient random number generation.

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

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

scramble
public void scramble(boolean guaranteeDifferent)
Randomly shuffles the permutation. Uses java.util.concurrent.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(Random 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(SplittableRandom 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 java.util.concurrent.ThreadLocalRandom as the source of efficient random number generation. 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, Random r)
Randomly shuffles a segment. 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 i, int j, SplittableRandom r)
Randomly shuffles a segment. 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, SplittableRandom r)
Randomly shuffles a noncontiguous 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, Random r)
Randomly shuffles a noncontiguous 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 noncontiguous 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 < iIndexOutOfBoundsException
 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 < iIndexOutOfBoundsException
 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[i1])==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 aswap(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 nonoverlapping 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 subarray 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 subarray to remove and insert (precondition: 0 ≤ i < length())size
 the length of the subarray (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 thePermutation(int,int)
constructor repeatedly incrementing the value passed for the second parameter. Specified by:
iterator
in interfaceIterable<Permutation>
 Returns:
 an Iterator

toString
public String toString()
Creates a String representing the permutation.

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.

