0

Suppose that I have a list x=[1, 2, 3, 4], it contains the sublists [1], [2], [3], [4], [1, 2], [2, 3], [3, 4], [1,2,3], [2,3,4] and [1,2,3,4]. But it does not contain something like [1, 3] because there is a gap as 2 appears between 1 and 3 in x.

Does anybody know what the best way is to test if a list is contained within another list without gap? I have thought about a for-loop solution, but it might not be a very good solution. Thanks.

Grijesh Chauhan
  • 57,103
  • 20
  • 141
  • 208
user1424739
  • 11,937
  • 17
  • 63
  • 152
  • 1
    Did you try ???, you can try using all possible substrings of a string e.g in '1234' a substring '13' is not possible – Grijesh Chauhan Jan 19 '14 at 13:57
  • Why do you want to check in the other list? Won't it be enough to check the list to be checked, whether all the elements are continuous? – thefourtheye Jan 19 '14 at 13:58

5 Answers5

3

Your question is:

Does anybody know what the best way is to test if a list is contained within another list without gap?

That's actually identical to the problem of finding a string in another string. And for that you have plenty of algorithms available.

Rabin–Karp, Boyer–Moore, Knuth–Morris, etc. I like the Boyer-Moore because of its simplicity. Have a look on the details on the Internet. Of course you could also check if you list is starting from any possible position, but the complexity is not optimal (you can find such solutions here: Check for presence of a sliced list in Python).

Here's a quick (and simplified) implementation for you:

def boyer(x, sublist):
    p = len(sublist) - 1
    i = 0
    while i + p < len(x):
        if x[i + p] == sublist[p]:
            if p == 0:
                return True
            p -= 1
        elif x[i + p] in sublist:
            i += 1
            p = len(sublist) - 1
        else:
            i = i + p + 1
            p = len(sublist) - 1
    return False

Note that this code should be tested carefully and is more about showing an alternative to the brute force approach. The time complexity of x[i + p] in sublist is linear and should be implemented differently to get a O(1) method. Currently, because of that, it won't be better than the brute force approach.

Community
  • 1
  • 1
Maxime Chéramy
  • 17,761
  • 8
  • 54
  • 75
2

You can try

' '.join(str(c) for c in list1) in ' '.join(str(c) for c in list2)
afkfurion
  • 2,767
  • 18
  • 12
1
sequences = [
    [1], [2],
    [1, 2], [2, 3], [3, 6],
    [1, 2, 3], [2, 3, 4], [1, 2, 3, 5],
]

bad_seq = lambda s: s and s != list(range(s[0], s[0] + len(s)))
print filter(bad_seq, sequences)   # [[3, 6], [1, 2, 3, 5]]
FMc
  • 41,963
  • 13
  • 79
  • 132
0

Just another solution, not sure the best of its kind, please let me know if i don't understand your question clearly.

ls = [[1], [2], [3], [4], [1, 2], [2, 3], [3, 6], [1, 2, 3], [2, 3, 4], [1, 2, 3, 5]]

def gap(l):
    for ls in l:
        result = list(set(map(lambda x: x[1] - x[0], zip(ls[0:], ls[1:]) )))
        if result and (len(result) > 1 or result[0] > 1):
            print ls
gap(ls)

Output: [3,6] [1, 2, 3, 5]

James Sapam
  • 16,036
  • 12
  • 50
  • 73
0

You can use numpy-diff function on indices of the sublist in the main list

In [427]: x=[1, 2, 3, 4]

In [428]: y = [1,3]

In [429]: z = [1,2,3]

In [430]: w = [2,1]

In [431]: import numpy as np

In [432]: sub_indices = [x.index(x1) for x1 in y]

Now, sub_indices should look like: [0, 2] So you can check the diff between the indices:

In [433]: np.all(np.diff(sub_indices) == 1)
Out[433]: False

In [434]: sub_indices = [x.index(x1) for x1 in z]

In [435]: np.all(np.diff(sub_indices) == 1)
Out[435]: True

In [436]: sub_indices = [x.index(x1) for x1 in w]

In [437]: np.all(np.diff(sub_indices) == 1)
Out[437]: False
mclafee
  • 1,406
  • 3
  • 18
  • 25