比较旋转的列表，包含重复项

Question

我正在寻找一种有效的方法来比较数字列表，看他们是否匹配在任何轮换（比较2个圆形列表）。

当列表中没有重复项时，选择最小/最大值并在比较工作前旋转两个列表。 但是，当可能有很多重复的大值时，这并不那么简单。

例如，列表[9, 2, 0, 0, 9]和[0, 0, 9, 9, 2]是匹配，
其中[9, 0, 2, 0, 9]不会（因为顺序不同）。

继承人是一个无效函数的例子。

def min_list_rotation(ls): 
    return min((ls[i:] + ls[:i] for i in range(len(ls)))) 

# example use 
ls_a = [9, 2, 0, 0, 9] 
ls_b = [0, 0, 9, 9, 2] 

print(min_list_rotation(ls_a) == min_list_rotation(ls_b)) 

这可以提高对效率...

• 检查排序的列表匹配运行详尽的测试之前。
• 只测试以最小值开始的旋转
  （在此之后跳过匹配值）
  有效地找到最小值和最后一个最小值（最后的最大值）（在多个匹配次最大值的情况下）。
• 比较转，而无需创建新的列表，每次..

但是它仍然不是一个非常有效的方法，因为它依赖于检查许多可能性。

是否有更有效的方式来执行此比较？

---

相关问题： Compare rotated lists in python

Answer 1

如果您在大量的名单正在寻找重复的，你可以每个列表旋转到其字典序最小的字符串表示，然后进行排序列表的列表或使用散列表查找重复项。这个规范化步骤意味着您不需要将每个列表与每个其他列表进行比较。在https://en.wikipedia.org/wiki/Lexicographically_minimal_string_rotation上有用于找到最小旋转的巧妙的O（n）算法。

Answer 2

你几乎拥有它。

你可以做一些“正常化”或“canonicalisation”独立于其他的名单，那么你只需要通过项目比较项目（或者，如果你想，把它们放在一个地图，在一组消除重复，...“

1取最小值项，这是不通过本身之前（以循环方式）

在你例如92009，应取第0（未第二个）

2如果您有总是同一项目（00000说），你只要记住这：00000

3如果有同一项目多次，采取下一个项目，这是小mal，并继续前进，直到找到一条具有最低限度的独特路径。

示例：90148301562 =>你有0148 ..和0156 .. =>你把0148

4如果不能分离不同的路径（=如果你有无限平等），您有一个重复的模式：那么，没关系：你拿走他们中的任何一个。

例如：014376501437650143765：你有相同的图案0143765 ...

它像AAA，其中A = 0143765

5当你有你在这张表单，很容易比较其中两个。

如何做有效：

迭代列表上，以获得最低MX（本身不是开头）。如果你找到几个，保留所有这些。

然后，从每个最小的Mx迭代，采取的下一个项目，并保持最低。如果您执行整个循环，则会有重复模式。

除重复图案的情况下，这必须是最小的方式。

希望它有帮助。

Answer 3

我会使用多项式散列函数来计算列表A的散列和列表B的每一个循环移位在哪里列表B的移具有相同的哈希值作为一览表A为此在预期O（N）时间，我会比较实际的元素，看看它们是否相等。

这很快的原因是，使用多项式哈希函数（这是非常常见的！），您可以计算在恒定时间内从前一个循环移位的哈希值，因此您可以计算所有循环的哈希值O（N）时间的变化。

它的工作原理是这样的：

假设B有N个元素，然后用素数p B的哈希值是：

Hb=0; 
for (i=0; i<N ; i++) 
{ 
    Hb = Hb*P + B[i]; 
} 

这是评估P中的多项式优化的方式，并相当于：

Hb=0; 
for (i=0; i<N ; i++) 
{ 
    Hb += B[i] * P^(N-1-i); //^ is exponentiation, not XOR 
} 

请注意每个B [i]是如何乘以P ^（N-1-i）的。如果我们将B向左移1，那么每个B [i]将乘以一个额外的P，除了第一个P。由于乘法是通过加法进行分配的，我们可以通过乘以整个散列来一次乘以所有的组件，然后修正第一个元素的因子。

B的左移的哈希只是

Hb1 = Hb*P + B[0]*(1-(P^N)) 

第二左移：

Hb2 = Hb1*P + B[1]*(1-(P^N)) 

等等...