6
\$\begingroup\$

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.

\$\endgroup\$
  • 2
    \$\begingroup\$ The description of what the method does in the class-level documentation seems much more accurate than the description given in the question. Given just the definition of the first sentence of the question I would write a method whose body is just ´return true;` because it seems to ask whether the permutation can be decomposed into cycles, and every permutation can be. \$\endgroup\$ – Peter Taylor Feb 22 at 11:15
  • \$\begingroup\$ @PeterTaylor: Indeed, that confused me first. en.wikipedia.org/wiki/Cyclic_permutation offers two definitions: “A permutation is called a cyclic permutation if and only if it has a single nontrivial cycle” vs “Some authors restrict the definition to only those permutations which consist of one nontrivial cycle”. – From the first sentence in the class-level documentation (and the implementation) it seems that the latter (stricter) definition is meant here. \$\endgroup\$ – Martin R Feb 22 at 12:31
  • \$\begingroup\$ On the other hand, the identity permutation of a single element (0) is not cyclic according to both definitions, but this code considers it to be cyclic – I am still confused! \$\endgroup\$ – Martin R Feb 22 at 12:46
7
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$

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");
      // ..
    }
  }
\$\endgroup\$
  • \$\begingroup\$ The current logic with && is still wrong, and the function names (e.g. “isOccurrenceOfAllElementsMoreThanOnce”) are confusing. – You probably mean if (isEmpty() || hasElementOutOfBounds() || hasDuplicateElements()) \$\endgroup\$ – Martin R Feb 22 at 11:56
  • \$\begingroup\$ @MartinR thank you! The suggested method names are much better \$\endgroup\$ – Roman Feb 22 at 12:05
  • \$\begingroup\$ For Permutation The check should go in the constructor and should throw IllegalArgumentException. For Permutations methods should be static. \$\endgroup\$ – abuzittin gillifirca Feb 22 at 15:25
1
\$\begingroup\$

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

\$\endgroup\$
1
\$\begingroup\$
/**
 * 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.

\$\endgroup\$
0
\$\begingroup\$

I see several flaws here:

  • It's wrong. It returns false for [0,1,2] or [1,0,2], which are a valid cyclic permutations. A permutation is cyclic if it contains at most one nontrivial cycle. [1,0,3,2] would be a non-cyclic permutation.

  • It throws on an empty array, which is a valid cyclic permutation. Return true instead.

  • It throws if there are duplicates or out-of-range values. Just return false to indicate it's not a cyclic permutation.

  • There are three passes over the array, which is unneccessary.

  • It allocates O(n) memory to check for duplicates, which is unneccessary.

  • The methods are not declared static, even though they are not stateful.

Below is a version that fixes all of the above. Note that duplicate elements always lead to infinite loops (you never get back to zero), so you can abort after you visited more numbers than there are elements.

public class Permutation
{
    public static bool isCyclic(int[] array)
    {
        // find the first out-of-place element
        int start = 0;
        while (start < array.length && array[start] == start)
        {
            start++;
        }

        // find the number of out-of-place elements, also check for out-of-bounds elements
        int length = 0;
        for (int i = start; i < array.length; i++)
        {
            if (array[i] < 0 || array[i] >= array.length)
            {
                return false;
            }
            if (array[i] != i)
            {
                length++;
            }
        }

        // no out-of-place elements, cyclic by definition
        if (length == 0)
        {
            return true;
        }

        // check if the cycle starting from the first out-of-place element contains
        // all out-of-place elements, which makes it the only cycle
        int visited = 1;
        for (int next = array[start]; next != start; next = array[next], visited++)
        {
            // we cannot have visited all elements without reaching start again, so we
            // must have been caught in an infinite loop due to duplicate elements
            if (visited == length)
            {
                return false;
            }
        }
        return visited == length;
    }
}
\$\endgroup\$
  • 2
    \$\begingroup\$ I am not very familiar with that topic, but there seem to be different definitions of what a cyclic permutation is. en.wikipedia.org/wiki/Cyclic_permutation offers “has a single nontrivial cycle” and “consists of one nontrivial cycle.” \$\endgroup\$ – Martin R Feb 22 at 12:49
  • \$\begingroup\$ Wolfram Alpha has a completely different definition from wikipedia. \$\endgroup\$ – abuzittin gillifirca Feb 25 at 6:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.