如何有效地比较两个循环(一个循环列表)并判断它们是否等价？

Question

循环/环是一种数据结构，可以表示为一个List，其中端点与begin连接。

旋转List不会改变它的意义，因为循环可以从任何元素开始读取。

只要保留了元素的序列，n元素的循环就可以用n不同的方式编写，因为确实存在n可能的旋转。

举个例子，下面的List都代表相同的环：

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

我希望找到一种有效的方法来判断两个给定的循环是否是等价的，因为它们可能是相同的，但是用两个不同的旋转来表示。

我已经考虑过一种“虚拟”的方法：

1. 通过Set检查两个列表的组成。
2. 如果它们是由相同的元素组成的，请检查元素的顺序如下：

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

希望在Java功能中已经有了一些现成的、更有效率的东西来完成我正在做的事情。

Answer 1

您要问的是如何比较两个相同的列表(a,b)，其中一个，比如a，已经有效地旋转了一个距离d，其中一个是1 <= d < a.size()。如果存在一些d，当应用于a时，它们将被认为是相等的，从而使a.equals(b)成为现实。

正如注释中所建议的那样，对于正确覆盖T的任何类型的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;
}

版画

[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]

备注：

• 这将适用于任何列表，但根据列表的大小以及它是否实现RandomAccess接口，可能会或多或少地提高效率。从JavaDoc on Collections.rotate。

如果指定的列表很小或实现了RandomAccess接口，这个实现将第一个元素交换到它应该去的位置，然后重复地将移位的元素交换到它应该去的位置，直到一个替换的元素被交换到第一个元素。必要时，在第二个和连续的元素上重复该过程，直到旋转完成为止。如果指定的列表很大，并且没有实现RandomAccess接口，则此实现将列表分解为索引-distance mod大小的两个子列表视图。然后在每个子列表视图上调用反向( list )方法，最后在整个列表上调用它。关于这两种算法的更完整的描述，请参阅Jon的编程珍珠2.3节(Addison，1986)。

• 我建议您在非常大的ArrayLists和LinkedLists上测试这一点，看看哪些最适合您的用例。
• 请注意，上面的方法更改了其中一个列表。这在输出中并不明显，因为更改的列表是在调用equals之前先打印出来的。为了防止这种情况，必须在比较之前复制其中一个列表，这也会降低性能。