我有这个功能用于确定一个列表是另一个列表旋转：

 高清isRotation（A，B）：
  如果len（A）= LEN（二）！
    返回False

  C = B * 2
  I = 0

  而[0] = C [I]！
    I + = 1

  对于x在：
    如果X = C [I]！
      返回False
    I + = 1

  返回True
 

例如。

 ＆GT;＆GT;＆GT;一个= [1,2,3]
＆GT;＆GT;＆GT; B = [2,3,1]
＆GT;＆GT;＆GT; isRotation（A，B）
真正
 

我如何使这项工作有重复？例如

  A = [3,1,2,3,4]
B = [3,4,3,1,2]
 

和它可以在进行O（N）时间？

您可以做到这一点在 0（N）时间和 0（1 ）使用的最大后缀算法的修改版本的空间：

从 Stringology 的宝石： 字循环平等

长度为n的话ü的旋转的形式为U [K + 1 ... N] [1 ... K]中的任何字。让U，W是同样的长度为n的两个单词。它们被说成是环状等效如果u（ⅰ）==瓦特（j）而某些I，J

如果单词u和w为写作圈子，他们是环状等价的，如果经过适当的旋转的圆圈重合。

有用于测试所述循环等价几个线性时间算法   两个词。最简单的是应用任何字符串匹配算法模式拍拍= u和文本= WW，因为字u和w为循环=等价的，如果拍发生在文本。

另一种算法是寻找UU和WW的最大后缀和检查   他们是在一个大小为prefixes相同。我们选择了这个问题，因为有更简单有趣的算法，在线性时间和常数空间同时，值得presentation工作。

 算法循环等价（U，W）
{检查的U和W共同长度为n的循环平等}
    X：= UU; Y：= WW;
    I：= 0;记者：= 0;
    而（ⅰn种）和（j n种）并开始
        K：= 1;
        而X [I + K] = Y [J + K]千万K：= K + 1;
        如果一个; ＆GT;接n返回true;
        如果x [I + K]≥ Y [I + K]然后我：= I + K别的记者：= J + K表;
        {}不变
    结束;
    返回false;
 

从而转化到Python就变成了：

 高清cyclic_equiv（U，V）：
    N，I，J = LEN（U），0，0
    如果n = LEN（V）！
        返回False
    而I＆LT; N和J＆LT; N：
        K = 1
        而K＆LT; = n和U [（I + K）％N] == v [（J + K）％N]：
            K + = 1
        如果K＆GT; N：
            返回True
        如果u [（I + K）％N]＆GT; v [（J + K）％N]：
            I + = K
        其他：
            J + = K
    返回False
 

运行的几个例子：

  [4]：A = [3,1,2,3,4]
在[5]：B = [3,4,3,1,2]
在[6]：cyclic_equiv（A，B）
出[6]：真
在[7]：B = [3,4,3,2,1]
在[8]：cyclic_equiv（A，B）
出[8]：假
在[9]：B = [3,4,3,2]
在[10]：cyclic_equiv（A，B）
出[10]：假
在[11]：cyclic_equiv（[1,2,3]，[1,2,3]）
出[11]：真
在[12]：cyclic_equiv（[3,1,2]，[1,2,3]）
出[12]：真
 

一个比较幼稚的方法是使用一个collections.deque旋转的元素：

 高清腐烂（L1，L2）：
    从收藏中导入双端队列
    如果L1 == 12：
        返回True
    ＃如果长度不同，我们不能让比赛
    如果len（12）= LEN（L1）！
        返回False
    ＃如果任何元素不同，我们不能让比赛
    如果设置（L1）.difference（12）：
        返回False
    12，L1 =双端队列（12），双端队列（L1）
    因为我在范围内（LEN（L1））：
        l2.rotate（）＃l2.appendleft（d.pop（））
        如果L1 == 12：
            返回True
    返回False
 

I have this function for determining if a list is a rotation of another list:

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

e.g.

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

How do I make this work with duplicates? e.g.

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

And can it be done in O(n)time?

You can do it in 0(n) time and 0(1) space using a modified version of a maximal suffixes algorithm:

From Jewels of Stringology: Cyclic equality of words

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 A; > n then return true;
        if x[i + k]> y[i + k] then i := i + k else j := j + k;
        { invariant }
    end;
    return false; 

Which translated to python becomes:

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

Running a few examples:

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

A more naive approach would be to use a collections.deque to rotate the elements:

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