Search code examples
javalistalgorithmperformanceequals

How to compare efficiently 2 cycles (a circular list) and tell if they equivalent?

A cycle/ring is a data structure representable as a List in which the end is connected with the begin.

Rotating the List doesn't change its meaning since a cycle can be read starting from whatever element.

As long the sequence of the elements it's preserved, cycles of n elements can be written in n different ways because there are exactly n possible rotations.

To make an example, the following List are all representing the same ring:

[0, 1, 2, 3]
[1, 2, 3, 0]
[2, 3, 0, 1]
[3, 0, 1, 2]

I am wishing to find an efficient way to tell if 2 given cycles are equivalent since they might be the same but represented with 2 different rotations.

I already considered a "dummy" approach:

  1. Check the composition of the 2 lists through Set.

  2. If they are made of the same elements check the sequence of elements as follow:

    • Go through the list2 until I find the element that is in the first position of list1;
    • Element by element check that list2 it's just a rotation of list1 considering that I might start back from index 0 in the list2 using mod function.

Hopefully there is something already out of the box and more efficient in the Java utils to accomplish what I'm doing.

Solution

  • What you're asking is how to compare two identical lists (a,b), one of which, say a, has been effectively rotated a distance d, where 1 <= d < a.size(). They would be considered equal if some d exists which, when applied to a, would make a.equals(b) true.

    As was suggested in the comments the following will do that for any type T that properly overrides equals.

    List<List<Object>> lists = List.of(
           new ArrayList<>(List.of("A","B","C",1,2)), new ArrayList<>(List.of("C",1,2,"A","B")),
           new ArrayList<>(List.of("A","B",1,2)), new ArrayList<>(List.of("B",1,2,"A")),
           new ArrayList<>(List.of(1,2,3,4)), new ArrayList<>(List.of(1,4,2,3)),
           new ArrayList<>(List.of("A","B","C","D")), new ArrayList<>(List.of("B","C","D","A")));

for(int i = 0; i < lists.size(); i+=2) {
       List<Object> l1 = lists.get(i);
       List<Object> l2 = lists.get(i+1);
        System.out.println(l1 + (equals(l1,l2) ? " equals " : " does not equal ") + l2); 
}
       
    

public static <T> boolean equals(List<T> list1, List<T> list2) {
    if (list1.size() == list2.size()) {
        for (int i = 0; i < list1.size(); i++) {
            if (list1.equals(list2)) {
                return true;
            }
            Collections.rotate(list1, 1);
        }
    }
    return false;
}

    prints

    [A, B, C, 1, 2] equals [C, 1, 2, A, B]
[A, B, 1, 2] equals [B, 1, 2, A]
[1, 2, 3, 4] does not equal [1, 4, 2, 3]
[A, B, C, D] equals [B, C, D, A]

    Notes:

    • this will work for any list but may be more or less efficient based on the size of the list and whether it implements the RandomAccess interface. From the JavaDoc on Collections.rotate.

    If the specified list is small or implements the RandomAccess interface, this implementation exchanges the first element into the location it should go, and then repeatedly exchanges the displaced element into the location it should go until a displaced element is swapped into the first element. If necessary, the process is repeated on the second and successive elements, until the rotation is complete. If the specified list is large and doesn't implement the RandomAccess interface, this implementation breaks the list into two sublist views around index -distance mod size. Then the reverse(List) method is invoked on each sublist view, and finally it is invoked on the entire list. For a more complete description of both algorithms, see Section 2.3 of Jon Bentley's Programming Pearls (Addison-Wesley, 1986).

    • I recommend you test this on very large ArrayLists and LinkedLists to see what best fits your use case.

    • Note that the above method alters one of the lists. This is not evident from the output since the list that is altered is printed first prior to calling equals. To prevent this, one of the lists must be copied prior to comparison which can also decrease performance.