# Issue

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:

Check the composition of the 2 lists through

`Set`

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

- Go through the

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.

Answered By - WJS Answer Checked By - Marilyn (PHPFixing Volunteer)

## 0 Comments:

## Post a Comment

Note: Only a member of this blog may post a comment.