# Q：检查列表是否与重复列表一起工作的另一个列表的旋转

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?

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

How do I make this work with duplicates? 例如

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

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

From Jewels of Stringology: Cyclic equality of words

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;
``````

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

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

The following meta-algorithm will solve it.

• Build a concatenation of a, e.g., a = [3,1,2,3,4] => aa = [3,1,2,3,4,3,1,2,3,4].

• Run any string adaptation of a string-matching algorithm, e.g., Boyer Moore to find b in aa.

One particularly easy implementation, which I would first try, is to use Rabin Karp as the underlying algorithm. In this, you would

• calculate the Rabin Fingerprint for b

• calculate the Rabin fingerprint for aa[: len(b)], aa[1: len(b) + 1], ..., and compare the lists only when the fingerprints match

Note that

• The Rabin fingerprint for a sliding window can be calculated iteratively very efficiently (read about it in the Rabin-Karp link)

• If your list is of integers, you actually have a slightly easier time than for strings, as you don't need to think what is the numerical hash value of a letter

• -

• Build a concatenation of a, 例如, a = [3,1,2,3,4] => aa = [3,1,2,3,4,3,1,2,3,4].

• Run any string adaptation of a string-matching algorithm, 例如, Boyer Moore to find b in aa.

• 计算B的拉宾指纹

• 计算拉宾指纹AA [：len（B）]、[ 1：AA len（B）+ 1 ]，…，并比较列表只有指纹匹配

• 滑动窗口的拉宾指纹可以非常有效地迭代计算（在Rabin Karp链接中读取）

• 如果你的列表是整数，你实际上比字符串稍微容易一些，因为你不需要考虑字母的数值哈希值

• -

I think you could use something like this:

``````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)
``````

Just common sense if we are talking about interview questions:

• we should remember that solution should be easy to code and to describe.
• do not try to remember solution on interview. It's better to remember core principle and re-implement it.

``````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)
``````

• we should remember that solution should be easy to code and to describe.
• do not try to remember solution on interview. It's better to remember core principle and re-implement it.

Alternatively (I couldn't get the b in aa solution to work), you can 'rotate' your list and check if the rotated list is equal to 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
``````

I believe this would be O(n) as it only has one for loop. Hope it helps

``````def is_rotation(a, b):

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

return False
``````

python  arrays  algorithm  time-complexity