How to check whether two lists are circularly identical in Python

by

First off, this can be done in O(n) in terms of the length of the list
You can notice that if you will duplicate your list 2 times ([1, 2, 3]) will be [1, 2, 3, 1, 2, 3] then your new list will definitely hold all possible cyclic lists.

So all you need is to check whether the list you are searching is inside a 2 times of your starting list. In python you can achieve this in the following way (assuming that the lengths are the same).

list1 = [1, 1, 1, 0, 0]
list2 = [1, 1, 0, 0, 1]
print ' '.join(map(str, list2)) in ' '.join(map(str, list1 * 2))

Some explanation about my oneliner:
list * 2 will combine a list with itself, map(str, [1, 2]) convert all numbers to string and ' '.join() will convert array ['1', '2', '111'] into a string '1 2 111'.

As pointed by some people in the comments, oneliner can potentially give some false positives, so to cover all the possible edge cases:

def isCircular(arr1, arr2):
    if len(arr1) != len(arr2):
        return False

    str1 = ' '.join(map(str, arr1))
    str2 = ' '.join(map(str, arr2))
    if len(str1) != len(str2):
        return False

    return str1 in str2 + ' ' + str2

P.S.1 when speaking about time complexity, it is worth noticing that O(n) will be achieved if substring can be found in O(n) time. It is not always so and depends on the implementation in your language (although potentially it can be done in linear time KMP for example).

P.S.2 for people who are afraid strings operation and due to this fact think that the answer is not good. What important is complexity and speed. This algorithm potentially runs in O(n) time and O(n) space which makes it much better than anything in O(n^2) domain. To see this by yourself, you can run a small benchmark (creates a random list pops the first element and appends it to the end thus creating a cyclic list. You are free to do your own manipulations)

from random import random
bigList = [int(1000 * random()) for i in xrange(10**6)]
bigList2 = bigList[:]
bigList2.append(bigList2.pop(0))

# then test how much time will it take to come up with an answer
from datetime import datetime
startTime = datetime.now()
print isCircular(bigList, bigList2)
print datetime.now() - startTime    # please fill free to use timeit, but it will give similar results

0.3 seconds on my machine. Not really long. Now try to compare this with O(n^2) solutions. While it is comparing it, you can travel from US to Australia (most probably by a cruise ship)

More Related Contents:

  1. Implement pow(x,n)%d with integers only. (without making use of library functions) [duplicate]
  2. Removing duplicates in lists
  3. How to generate all permutations of a list?
  4. How to split text without spaces into list of words
  5. Understanding recursion in Python
  6. Find all combinations of a list of numbers with a given sum
  7. Why is Bubble Sort implementation looping forever?
  8. Edit Distance in Python
  9. Find longest repetitive sequence in a string
  10. Python string ‘in’ operator implementation algorithm and time complexity
  11. Speed of calculating powers (in python)
  12. heapq with custom compare predicate
  13. Simple Python Challenge: Fastest Bitwise XOR on Data Buffers
  14. Algorithm to find which number in a list sum up to a certain number
  15. Checking if all elements in a list are unique
  16. When splitting an empty string in Python, why does split() return an empty list while split(‘\n’) returns [”]?
  17. Weighted random sample in python
  18. General bars and stars
  19. Python Integer Partitioning with given k partitions
  20. What is the complexity of the sorted() function?
  21. Non biased return a list of n random positive numbers (>=0) so that their sum == total_sum
  22. “For” loop first iteration
  23. Sliding window maximum in O(n) time
  24. How to hash a string into 8 digits?
  25. NumPy grouping using itertools.groupby performance
  26. A set union find algorithm
  27. Finding the most frequent character in a string
  28. Handling big numbers in code
  29. What is this odd sorting algorithm?
  30. counting combinations and permutations efficiently

Leave a Comment