Checking if an integer permutation is cyclic in Java 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 &lt; array.length; i++) {
            int num = array[i];

            if (num &lt; 0 || num &gt;= 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] &gt; 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.
Here


int nextNumber = array[array[0]];
int visitedNumbers = 1;

while (nextNumber != array[0]) {
    nextNumber = array[nextNumber];
    visitedNumbers++;
}



you determine the length of the orbit starting array[0]. If you start at 0 instead then some array lookups are saved, and I find it easier to understand:

int nextNumber = array[0];
int visitedNumbers = 1;

while (nextNumber != 0) {
    nextNumber = array[nextNumber];
    visitedNumbers++;
}


And with a do-while loop the initial array lookup can be made part of the loop:

int currentNumber = 0;
int visitedNumbers = 0;

do {
    currentNumber = array[currentNumber];
    visitedNumbers++;
} while (currentNumber != 0);




Further suggestions:

Checking for duplicate array elements is not necessary if you limit the number of iterations:

int currentNumber = 0;
int visitedNumbers = 0;

do {
    currentNumber = array[currentNumber];
    visitedNumbers++;
} while (visitedNumbers &lt;= array.length &amp;&amp; currentNumber != 0);


This saves one array traversal and the additional storage in checkArrayElements(). The only downside is that calling the function with an invalid permutation now possibly returns false instead of throwing an error.

Similarly, the “bounds check” can be made directly in that loop. That might be viewed as a violation of the “separation of concerns” principle, but saves one array traversal.