A an integer permutation array[] is said to be cyclic if and only if we can choose an arbitrary element at position i, move it to the array[i]'s position, move the array[i]'s element to array[array[i]]'s position, and finally end up to the ith position. For example, \$\langle 1, 2, 0 \rangle\$ is cyclic, whereas \$\langle 1, 0, 2 \rangle\$ is not since if we start from 2, we sill end up in an infinite loop. My attempt is as follows:
package net.coderodde.math;
import java.util.Objects;
/**
* This class checks that a given permutation consists of a single cycle
* covering the entire sequence. The idea is that if the input array is
* {@code 1, 0, 2}, it returns {@code false} since 2 is in its correct position.
* On the other hand, {@code 1, 2, 0} returns {@code true} since it consists of
* only one permutation cycle.
*
* @author Rodion "rodde" Efremov
* @version 1.6 (Feb 22, 2019)
*/
public class PermutationCyclicity {
private static final String NUMBER_OUT_OF_BOUNDS_EXCEPTION_FORMAT =
"array[%d] = %d, array.length = %d";
public boolean isCyclic(int[] array) {
check(array);
int nextNumber = array[array[0]];
int visitedNumbers = 1;
while (nextNumber != array[0]) {
nextNumber = array[nextNumber];
visitedNumbers++;
}
return visitedNumbers == array.length;
}
private void check(int[] array) {
checkArrayHasLength(array);
checkArrayContentsWithinBounds(array);
checkArrayElements(array);
}
private void checkArrayHasLength(int[] array) {
Objects.requireNonNull(array, "The input array is null.");
if (array.length == 0) {
throw new IllegalArgumentException("The array has length zero.");
}
}
private void checkArrayContentsWithinBounds(int[] array) {
for (int i = 0; i < array.length; i++) {
int num = array[i];
if (num < 0 || num >= array.length) {
String exceptionMessage =
String.format(NUMBER_OUT_OF_BOUNDS_EXCEPTION_FORMAT,
i,
num,
array.length);
throw new IllegalArgumentException(exceptionMessage);
}
}
}
private void checkArrayElements(int[] array) {
int[] counts = new int[array.length];
for (int i : array) {
if (++counts[i] > 1) {
throw new IllegalArgumentException(
"The value " + i + " appears more than once.");
}
}
}
public static void main(String[] args) {
PermutationCyclicity pc = new PermutationCyclicity();
System.out.println(pc.isCyclic(new int[] { 1, 2, 3, 0 }));
try {
pc.isCyclic(new int[] { 1, 0, 1 });
} catch (Exception ex) {
System.out.println(ex.getMessage());
}
try {
pc.isCyclic(new int[] { 1 });
} catch (Exception ex) {
System.out.println(ex.getLocalizedMessage());
}
System.out.println(pc.isCyclic(new int[] { 1, 0, 2 }));
}
}
Critique request
I would like to hear comments regarding exception throwing and naming conventions, yet feel free to tell me anything that comes to mind.
