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.

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 <= array.length && 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.

For the task to check if a permutation is cyclic, the code works perfect. But we have no reusable code because it works only for these task, since the methods checkArrayHasLength, checkArrayContentsWithinBounds and checkArrayElements are private, return void and throw an IllegalArgumentException.

Null Checking

The method checkArrayHasLength checks for null, but checkArrayElements doesn`t.

So the method checkArrayElements is dependent on checkArrayHasLength in the method check and you can't call them in an different order without to get your personalized exception message.

checkArrayHasLength(null); // personalized error message

checkArrayElements(null); // non personalized error message

Naming

After I looked into checkArrayHasLength I understand, that it means it checks if an array is not empty. For me, maybe because I'm not a native English speaker, the name checkArrayIsNotEmpty would be better.

The name checkArrayElements is in my eyes useless. This name could use every method that do some validation on an array. I think the name checkAllArrayElementsOccurNotMoreThanOnce would be better.

Type Embedded in Name

Avoid placing types in method names; it's not only redundant, but it forces you to change the name if the type changes.

Each method includes Array, which is redundant because the parameter list already includes the datatype. If you want to switch from an array to a list you need to rename all methods and it could be possible to forget one method..

New method names could be: checkIsNotEmpty, checkElementsWithinBounds and checkAllElementsOccurNotMoreThanOnce.

Make it more Abstract

As already mention you have three methods that are private, but they could be public to.

Rename PermutationCyclicity

If we rename PermutationCyclicity to Permutation it would make sense to have methods that check for the length, the bounds and the number of occurrence of elements. These methods could now return a boolean instead of void and for that I would suggest to rename again all methods with an is or are prefix instead of check.

As a Utility-Class

class Permutations {



  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) {

    if (isNotEmpty(array))

      throw new IllegalArgumentException("The array has length zero.");

    if (areAllElementsWithinBounds(array))

      throw new IllegalArgumentException("Argument contains elements that are not in the bound");

    if (isOccurrenceOfAllElementsNotMoreThanOnce(array))

      throw new IllegalArgumentException("Argument contains elements that occurs multiple times");

  }



  public boolean isNotEmpty(int[] array) {* ... *}



  public boolean areAllElementsWithinBounds(int[] array) {* ... *}



  public boolean isOccurrenceOfAllElementsNotMoreThanOnce(int[] array) {* ... *}



}

As a Value-Object

class Permutation {



  private int[] values;



  public Permutation(int[] values) {

    this.values = Objects.requireNonNull(values, "The argument is null.");

  }



  public boolean isCyclic() {

    check();

    int nextNumber = values[values[0]];

    int visitedNumbers = 1;



    while (nextNumber != values[0]) {

      nextNumber = values[nextNumber];

      visitedNumbers++;

    }



    return visitedNumbers == values.length;

  }



  private void check() {

    if (isNotEmpty())

      throw new IllegalArgumentException("The array has length zero.");



    if (areAllElementsWithinBounds())

      throw new IllegalArgumentException("Argument contains elements that are not in the bound");



    if (isOccurrenceOfAllElementsNotMoreThanOnce())

      throw new IllegalArgumentException("Argument contains elements that occurs multiple times");

  }



  public boolean isNotEmpty() {* ... *}



  public boolean areAllElementsWithinBounds() {* ... *}



  public boolean isOccurrenceOfAllElementsNotMoreThanOnce() {* ... *}



}

Does it need to Throw?

I'm not if the method isCyclic needs to throw an IllegalArgumentException. From my feelings here a permutation can be cyclic or not - true or false. Additional if a client forgot to catch the IllegalArgumentException, he will never get to know the reason.

If you want to make sure the client should get always the reason use not a RuntimeException, because they don't have to be checked.

A other way would to use an algebraic data type. The Either can be used to get a result or an error message.

Or just simply return false and the client has to find the reason:

class Permutation {



  private int[] values;



  public Permutation(int[] values) {

    this.values = Objects.requireNonNull(values, "The argument is null.");

  }



  public boolean isCyclic() {

    if (isEmpty() 

        && areAllElementsAreNotWithinBounds() 

        && isOccurrenceOfAllElementsMoreThanOnce())

      return false;



    // ..



    return visitedNumbers == values.length;

  }



  public boolean isEmpty() {* ... *}



  public boolean areAllElementsAreNotWithinBounds() {* ... *}



  public boolean isOccurrenceOfAllElementsMoreThanOnce() {* ... *}



}

public static void main(String[] args) {

    Permutation permutation = new Permutation(new int[] {1, 2, 3, 0});



    if (permutation.isCyclic())

      System.out.println("nice");

    else {

      if (!permutation.areAllElementsWithinBounds())

        System.out.println("not all elements are in bound");

      // ..

    }

  }

I would prefer checkArrayValidity over the generic check and PermutationCyclicityChecker checker over PermutationCyclicity as the class implements functionality, not state.

Maybe move exception message formatting to dedicated exception classes and unify the message format in all cases (one provides indexes where error occurs, the other just the offending value).