检查一个列表是否是另一个列表的轮换，该列表适用于重复项

Question

我有这个函数来确定一个列表是否是另一个列表的轮换：

def isRotation(a,b):
  if len(a) != len(b):
    return False

  c=b*2
  i=0

  while a[0] != c[i]:
    i+=1

  for x in a:
    if x!= c[i]:
      return False
    i+=1

  return True

例如

>>> a = [1,2,3]
>>> b = [2,3,1]
>>> isRotation(a, b)
True

如何使用重复项进行这项工作？例如

a = [3,1,2,3,4]
b = [3,4,3,1,2]

能在O(n)时间内完成吗？

Answer 1

我想你可以使用这样的东西：

a1 = [3,4,5,1,2,4,2]
a2 = [4,5,1,2,4,2,3]

# Array a2 is rotation of array a1 if it's sublist of a1+a1
def is_rotation(a1, a2):
   if len(a1) != len(a2):
       return False

   double_array = a1 + a1

   return check_sublist(double_array, a2)

def check_sublist(a1, a2):
   if len(a1) < len(a2):
       return False

   j = 0
   for i in range(len(a1)):
        if a1[i] == a2[j]:
              j += 1
        else:
              j = 0

        if j == len(a2):
              return True

   return j == len(a2)

如果我们谈论的是面试问题，那就是常识：

我们应该记住，解决方案应该易于编码和描述。
面试时不要试图记住答案。最好记住核心原则并重新实现它。

Answer 2

下面的元算法将解决它。

构建 a 的串联，例如 a = [3,1,2,3,4] => aa = [3,1,2,3,4,3,1,2,3,4].
运行字符串匹配算法的任何字符串改编，例如，Boyer Moore 在 aa.[=21= 中查找 b ]

我首先尝试的一个特别简单的实现是使用 Rabin Karp 作为基础算法。在这方面，你会

为b

Rabin Fingerprint

计算 aa[: len(b)], aa[1: len(b) + 1], ... 的 Rabin 指纹，仅当指纹匹配时比较列表

注意

滑动的 Rabin 指纹 window 可以非常有效地迭代计算（在 Rabin-Karp link 中阅读）
如果你的列表是整数，你实际上比字符串稍微容易一些，因为你不需要考虑字母的数字哈希值是什么

Answer 3

或者（我无法使 b in aa 解决方案起作用），您可以 'rotate' 您的列表并检查旋转列表是否等于 b:

def is_rotation(a, b):

    for n in range(len(a)):
        c = c = a[-n:] + a[:-n]
        if b == c:
            return True

    return False

我相信这会是 O(n)，因为它只有一个 for 循环。希望对你有帮助

Answer 4

您可以在 0(n) 时间和 0(1) space 内完成，使用最大后缀算法的修改版本：

来自 Jewels of Stringology： 单词循环相等

A rotation of a word u of length n is any word of the form u[k + 1...n][l...k]. Let u, w be two words of the same length n. They are said to be cyclic-equivalent if u(i) == w(j) for some i, j.

If words u and w are written as circles, they are cyclic-equivalent if the circles coincide after appropriate rotations.

There are several linear-time algorithms for testing the cyclic-equivalence of two words. The simplest one is to apply any string matching algorithm to pattern pat = u and text = ww because words u and w are cyclic=equivalent if pat occurs in text.

Another algorithm is to find maximal suffixes of uu and ww and check if they are identical on prefixes of size n. We have chosen this problem because there is simpler interesting algorithm, working in linear time and constant space simultaneously, which deserves presentation.

Algorithm Cyclic-Equivalence(u, w)
{ checks cyclic equality of u and w of common length n }
    x := uu; y := ww;
    i := 0; j := 0;
    while (i < n) and (j < n) do begin
        k := 1;
        while x[i + k] = y[j + k] do k := k + 1;
        if k > n then return true;
        if x[i + k]> y[i + k] then i := i + k else j := j + k;
        { invariant }
    end;
    return false;

翻译成 python 变成：

def cyclic_equiv(u, v):
    n, i, j = len(u), 0, 0
    if n != len(v):
        return False
    while i < n and j < n:
        k = 1
        while k <= n and u[(i + k) % n] == v[(j + k) % n]:
            k += 1
        if k > n:
            return True
        if u[(i + k) % n] > v[(j + k) % n]:
            i += k
        else:
            j += k
    return False

运行几个例子：

In [4]: a = [3,1,2,3,4]   
In [5]: b =[3,4,3,1,2]   
In [6]: cyclic_equiv(a,b)
Out[6]: True    
In [7]: b =[3,4,3,2,1]    
In [8]: cyclic_equiv(a,b)
Out[8]: False    
In [9]: b =[3,4,3,2]    
In [10]: cyclic_equiv(a,b)
Out[10]: False
In [11]: cyclic_equiv([1,2,3],[1,2,3])
Out[11]: True
In [12]: cyclic_equiv([3,1,2],[1,2,3])
Out[12]: True

更简单的方法是使用 collections.deque 来旋转元素：

def rot(l1,l2):
    from collections import deque
    if l1 == l2:
        return True
    # if length is different we cannot get a match
    if len(l2) != len(l1):
        return False
    # if any elements are different we cannot get a match
    if set(l1).difference(l2):
        return False
    l2,l1 = deque(l2),deque(l1)
    for i in range(len(l1)):
        l2.rotate() # l2.appendleft(d.pop()) 
        if l1 == l2:
            return True
    return False

Answer 5

这似乎有效。

def func(a,b):
    if len(a) != len(b):
        return False
    elif a == b:
        return True

    indices = [i for i, x in enumerate(b) if x == a[0] and i > 0]

    for i in indices:
        if a == b[i:] + b[:i]:
            return True

    return False

还有这个：

def func(a, b):
    length = len(a)

    if length != len(b):
         return False

    i = 0
    while i < length:
        if a[0] == b[i]:
            j = i
            for x in a:
                if x != b[j]:
                    break
                j = (j + 1) % length
            return True
        i += 1

    return False

Answer 6

如果您可以将它们表示为字符串，只需执行以下操作：

def cyclically_equivalent(a, b):
    return len(a) == len(b) and a in 2 * b

否则，应该得到一个子列表搜索算法，比如Knuth-Morris-Pratt（Google给出了一些实现）和do

def cyclically_equivalent(a, b):
    return len(a) == len(b) and sublist_check(a, 2 * b)

Answer 7

您可以尝试测试仅使用 deque 集合中的 rotate() 函数的性能：

from collections import deque

def is_rotation(a, b):

    if len(a) == len(b):
        da = deque(a)
        db = deque(b)

        for offset in range(len(a)):
            if da == db:
                return True

            da.rotate(1)

    return False

在性能方面，对于小数组需要多次计算，还是对于非常大的数组需要计算几次？这将决定特殊情况测试是否会加快速度。

Answer 8

Knuth-Morris-Pratt algorithm 是一种字符串搜索算法，运行时间复杂度为 O(n)，其中 n 是文本 S 的长度（假设存在预先构造的 table T，运行时间复杂度为 O(m ) 其中 m 是搜索字符串的长度)。总而言之就是 O(n+m).

你可以做一个类似的受 KMP 启发的模式匹配算法。

将一个列表连接到自身，例如 a+a 或 b+b - 这是搜索到的 text/list 和 2*n 个元素
基于其他列表（b 或 a）构建 table T - 这在 O(n)
运行受 KMP 启发的算法 - 这是在 O(2*n) 中完成的（因为您将列表连接到自身）

Overall time complexity is O(2*n+n) = O(3*n) which is in O(n)

检查一个列表是否是另一个列表的轮换，该列表适用于重复项

Check if a list is a rotation of another list that works with duplicates

python

arrays

algorithm

time-complexity