In Python it is efficient to determine if two lists are shifted together

Question

What is the most effective (in time) way to check whether two relatively short (about 3-8 items) lists are shifted to each other? And if so, identify and return the offset?

Here is an example of the code and output that I would like:

>>> def is_shifted_copy(list_one, list_two): >>> # TODO >>> >>> is_shifted_copy([1, 2, 3], [1, 2, 3]) 0 >>> is_shifted_copy([1, 2, 3], [3, 1, 2]) 1 >>> is_shifted_copy([1, 2, 3], [2, 3, 1]) 2 >>> is_shifted_copy([1, 2, 3], [3, 2, 1]) None >>> is_shifted_copy([1, 2, 3], [1]) None >>> is_shifted_copy([1, 1, 2], [2, 1, 1]) 1 

Lists may contain duplicate entries. If more than one offset is allowed, return any offset.

Answer 1

Finding two copies of the first list avoids excessive concatenation:

 def is_shifted_copy(l1, l2): l1l1 = l1 * 2 n = len(l1) return next((i for i in range(n) if l1l1[i:i + n] == l2), None) 

Answer 2

here is a simple version of an iterator that does the job in 2n iterations (n ​​is the length of the list)

 import itertools def is_shifted_copy(list1, list2): if len(list1) != len(list2): return False iterator = iter(list2) for i, item in enumerate(itertools.chain(list1, list1)): try: if item == iterator.next(): continue else: iterator = iter(list2) except StopIteration: return i - len(list2) else: return False print is_shifted_copy([1, 2, 3], [1, 2, 3]) #0 print is_shifted_copy([1, 2, 3], [3, 1, 2]) #2 print is_shifted_copy([1, 2, 3], [3, 2, 1]) #False print is_shifted_copy([1, 2, 3], [2, 3, 1]) #1 print is_shifted_copy([1, 1, 2], [2, 1, 1]) #2 print is_shifted_copy([1, 2, 3], [1]) #False print is_shifted_copy([1, 2, 1], [2, 1, 1]) #1 print is_shifted_copy([1, 1, 1], [1, 1, 1]) #0 

and from your specification

should not is_shifted_copy([1, 1, 2], [2, 1, 1]) return 2 ?

Answer 3

Here is a solution based on indexes and slicing:

 >>> def is_shifted_copy(l1, l2): try: return [l1[-i:] + l1[:-i] for i in range(len(l1))].index(l2) except ValueError: return None 

The result will be as expected:

 >>> is_shifted_copy([1, 2, 3], [1, 2, 3]) 0 >>> is_shifted_copy([1, 2, 3], [3, 1, 2]) 1 >>> is_shifted_copy([1, 2, 3], [2, 3, 1]) 2 >>> is_shifted_copy([1, 2, 3], [2, 1, 3]) None 

Answer 4

Below is a modified version of the NPE solution that checks all possible match items. It compares favorably with the smart solutions of the thkang (and ecatmur's) iterator:

 import itertools as IT def is_shifted_copy_thkang(list1, list2): N = len(list1) if N != len(list2): return None elif N == 0: return 0 next_item = iter(list2).next for i, item in enumerate(IT.chain(list1, list1)): try: if item == next_item(): continue else: next_item = iter(list2).next except StopIteration: return -i % N else: return None def is_shifted_copy_NPE(list1, list2): N = len(list1) if N != len(list2): return None elif N == 0: return 0 pos = -1 first = list1[0] while pos < N: try: pos = list2.index(first, pos+1) except ValueError: break if (list2 + list2)[pos:pos+N] == list1: return pos return None def is_shifted_copy_ecatmur(l1, l2): l1l1 = l1 * 2 n = len(l1) return next((-i % n for i in range(n) if l1l1[i:i + n] == l2), None) tests = [ # ([], [], 0), ([1, 2, 3], [1, 2, 3], 0), ([1, 2, 3], [3, 1, 2], 1), ([1, 2, 3], [2, 3, 1], 2), ([1, 2, 3], [3, 2, 1], None), ([1, 2, 3], [1], None), ([1, 1, 2], [2, 1, 1], 1), ([1,2,3,1,3,2], [1,3,2,1,2,3], 3) ] for list1, list2, answer in tests: print(list1, list2, answer) assert is_shifted_copy_thkang(list1, list2) == answer assert is_shifted_copy_NPE(list1, list2) == answer assert is_shifted_copy_ecatmur(list1, list2) == answer 

---

 In [378]: %timeit is_shifted_copy_thkang([1, 2, 3], [3, 1, 2]) 100000 loops, best of 3: 3.5 us per loop In [377]: %timeit is_shifted_copy_ecatmur([1, 2, 3], [3, 1, 2]) 100000 loops, best of 3: 2.37 us per loop In [379]: %timeit is_shifted_copy_NPE([1, 2, 3], [3, 1, 2]) 1000000 loops, best of 3: 1.13 us per loop 

---

Note. I changed the return value to is_shifted_copy_thkang and is_shifted_copy_ecatmur so that all three versions pass the tests to the original message.

I compared functions with and without changes and found that this does not have a significant effect on the performance of functions.

For example, with return i :

 In [384]: %timeit is_shifted_copy_thkang([1, 2, 3], [3, 1, 2]) 100000 loops, best of 3: 3.38 us per loop 

With return -i % N :

 In [378]: %timeit is_shifted_copy_thkang([1, 2, 3], [3, 1, 2]) 100000 loops, best of 3: 3.5 us per loop