找到你要的答案

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

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]

它可以在O(N)的时间吗?

answer1: 回答1:

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

你能在0做的(N)和0(1)使用修改后的版本空间最大后缀算法:

From Jewels of Stringology: Cyclic equality of words

一个字的长度u的旋转是任何形式的U + K + 1……n […]。让u,W是两个相同长度的字。他们说是循环等价,如果u(i)= W(j)的一些我,J.

如果单词U和W写为圆,它们是循环等价的,如果圆重合后适当的旋转。

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; 

翻译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
answer2: 回答2:

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.


一个特别简单的实现,我会首先尝试,是使用Rabin Karp作为底层算法。在此,你会

  • 计算B的拉宾指纹

  • 计算拉宾指纹AA [:len(B)]、[ 1:AA len(B)+ 1 ],…,并比较列表只有指纹匹配

请注意,

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

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

  • -
answer3: 回答3:

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.
answer4: 回答4:

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

或者(我不能得到B的AA解决方案的工作),你可以'旋转'您的清单,并检查是否旋转列表等于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),因为它只有一个循环。希望有帮助

python  arrays  algorithm  time-complexity