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. 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 checkArrayForDuplicateElements 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, checkForElementOutOfBounds and checkForDuplicateElements.

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, are or has 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 (hasElementOutOfBounds(array))

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

    if (hasDuplicateElements(array))

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

  }



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



  public boolean hasElementOutOfBounds(int array) {* ... *}



  public boolean hasDuplicateElements(int array) {* ... *}



}

As a First Class Collection

The First Class Collection is an idea of the Object Calisthenics.

Any class that contains a collection should contain no other member variables. Each collection gets wrapped in its own class, so now behaviors related to the collection have a home.

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 (hasElementOutOfBounds())

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



    if (hasDuplicateElements())

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

  }



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



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



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



}

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() || hasElementOutOfBounds() || hasDuplicateElements())

      return false;



    // ..



    return visitedNumbers == values.length;

  }



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



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



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



}

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

/**

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

 */

I find the description clear, although I might reword from "The idea is that..." to

For example, given {@code 1, 0, 2}, it returns {@code false} because that permutation

consists of two disjoint cycles {@code (1, 0), (2)}.

I'm not clear on why this check should need a class for itself. I would expect either to have a Permutation class which could have an instance isCyclic method, or to have a PermutationUtils class with a static isCyclic method.

    private static final String NUMBER_OUT_OF_BOUNDS_EXCEPTION_FORMAT = 

            "array[%d] = %d, array.length = %d";

Thumbs up for this. I'm always glad to see details in exception messages.

    public boolean isCyclic(int array) {

No method-level javadoc? At the very least, I would like to see something telling me that the class considers that the empty array is not a valid permutation, because I think it is.

array is not a useful name. I would go with perm; others would prefer to avoid the abbreviation and call it permutation. I can also see an argument for pi as that is the symbol most commonly used to represent a permutation.

        check(array);

Check what? How about checkIsValidPermutation?

        int nextNumber = array[array[0]];

        int visitedNumbers = 1;



        while (nextNumber != array[0]) {

            nextNumber = array[nextNumber];

            visitedNumbers++;

        }



        return visitedNumbers == array.length;

Coming back to my earlier comment about PermutationUtils: I find it hard to envisage a library which has a need for isCyclic but not for finding the cycle decomposition of a permutation, so I'm surprised that the implementation isn't return cycleDecomposition(array).length == 1;

    private void check(int array) {

        checkArrayHasLength(array);

        checkArrayContentsWithinBounds(array);

        checkArrayElements(array);

    }

I see this as really two checks: checkNotNullOrEmpty and checkIsPermutation. Of course, if you use a Permutation class then these would be handled by the constructor and at most you'd have to check that the array is not empty.

    public static void main(String args) {

        PermutationCyclicity pc = new PermutationCyclicity();

        System.out.println(pc.isCyclic(new int { 1, 2, 3, 0 }));

A good unit test compares the observed value / behaviour against the expected value / behaviour. This test requires you to either remember the expected output or figure it out from first principles when you come back to maintain the code.