1

I need to write a function where I need to check if two lists with elements like these

(['E', 'A', None, 'D', 'B', None, None, 'C'], ['B', None, None, 'C', 'E', 'A', None, 'D'])

have the same elements, in the same order, but with other starting points.

So if you search 'E' in the second list, and take that as starting point, you get:

(['E', 'A', None, 'D', 'B', None, None, 'C'], ['E', 'A', None, 'D', 'B', None, None, 'C'])

These two are the same, so they have to return True.

If they are not the same, it needs to return False.

I'm sorry for the duplicate, I'm not a native english speake and didn't knew how to express it

Arne De Visscher
  • 33
  • 3
  • 3
    Hi! Welcome to the site! How far have you got? What is it you've got stuck on? Can you include some code in your answer? – msturdy Dec 09 '14 at 11:50
  • 1
    Also, check [how to check whether two lists are circularly identical](http://stackoverflow.com/questions/26924836/how-to-check-whether-two-lists-are-circularly-identical) and [fastest way to prove linked list is circular in python](http://stackoverflow.com/questions/20353835/fastest-way-to-prove-linked-list-is-circular-in-python) – fredtantini Dec 09 '14 at 11:58

3 Answers3

1

If you can reliably serialise the lists to strings, then you can easily do this using a cheap and fast substring check.

A similar question was asked recently, and here is this basic idea stolen from there:

l1 = ['E', 'A', None, 'D', 'B', None, None, 'C']
l2 = ['B', None, None, 'C', 'E', 'A', None, 'D']

if len(l1) == len(l2) and set(l1) == set(l2):    
    sep = ' '  # choose something that won't be in the data
    str_2l1 = sep.join(repr(x) for x in l1 + l1)
    str_l2 = sep.join(repr(x) for x in l2)
    return str_l2 in str_2l1
else:
    return False
Community
  • 1
  • 1
wim
  • 338,267
  • 99
  • 616
  • 750
0

You can leverage difflib.get_matching_block to easily solve the problem.

NOte There can be algorithm more efficient than this, but you didn't ask for the most efficient.

Implementation

def is_same(l1, l2):
    import difflib
    sm = difflib.SequenceMatcher(None, *l)
    a, b, s = sm.get_matching_blocks()[0]
    if s:
        return l1 == l2[b:] + l2[:b2]
    return false

Alternate Implementation

def is_same(l1, l2):
    import difflib
    sm = difflib.SequenceMatcher(None, l[0], l[1]*2)
    a, b, s = sm.get_matching_blocks()[0]
    return s == len(l1)

Example

>>> l = (['E', 'A', None, 'D', 'B', None, None, 'C'], ['B', None, None, 'C', 'E', 'A', None, 'D'])
>>> is_same(*l)
True
Abhijit
  • 62,056
  • 18
  • 131
  • 204
-3

This really depends on the types of lists you're using. For example, the problem is immensely simplified if you know that at least one element, for example 'A', appears exactly once in any list you have. If this is the case, you could do something like:

list1 = [your first list]
list2 = [your second list]

for i in range(len(list1)):
    if list1[i] == 'A':
        split1A, split1B = list1[i:], list1[:i]
        check1 = split1A + split1B

#Repeat for list2

if check1 == check2: return True
else: return False

Really, the complexity of the answer depends on the nature of the lists.

Johan
  • 343
  • 1
  • 4
  • 13