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

Question

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?

Answer 1

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

-

Answer 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 k > 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

Answer 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.

Answer 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

Answer 5

This seems to work.

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

And this also:

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

If you can represent these as strings instead, just do:

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

Otherwise, one should get a sublist searching algorithm, such as Knuth-Morris-Pratt (Google gives some implementations) and do

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

Answer 7

You could try testing the performance of just using the rotate() function in the deque collection:

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

In terms of performance, do you need to make this calculation many times for small arrays, or for few times on very large arrays? This would determine whether or not special case testing would speed it up.

Answer 8

Knuth-Morris-Pratt algorithm is a string search algorithm that runs in O(n) where n is the length of a text S (assuming the existence of preconstructed table T, which runs in O(m) where m is the length of the search string). All in all it is O(n+m).

You could do a similar pattern matching algorithm inspired by KMP.

• Concatenate a list to itself, like a+a or b+b - this is the searched text/list with 2*n elements
• Build the table T based on the other list (be it b or a) - this is done in O(n)
• Run the KMP inspired algorithm - this is done in O(2*n) (because you concatenate a list to itself)

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