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 oflist1
; - Element by element check that
list2
it's just a rotation oflist1
considering that I might start back from index 0 in thelist2
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
andLinkedLists
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 - Candace Johnson (JavaFixing Volunteer)