How to test membership of sequence in python list? [duplicate]

Question

This question already has answers here:

Best way to determine if a sequence is in another sequence? (10 answers)

Closed 9 years ago.

I have a dictionary which consists of {str: list}.

What I want to do is find out the keys with specific sequnce that may exist in value.

for example, the content of dictionary is like this:

DOC3187 [1, 2, 3, 6, 7]
DOC4552 [5, 2, 3, 6]
DOC4974 [1, 2, 3, 6]
DOC8365 [1, 2, 3, 5, 6, 7]
DOC3738 [1, 4, 2, 3, 6]
DOC5311 [1, 5, 2, 3, 6, 7]

and I need to find out the keys with sequence of [5,2,3], so desired return should be:

DOC4552, DOC5311

I'm using Python 3.3.2, and the dictionary has about 400 items.

Answer 1

NOTE: I realized that this will actually fail if your list contains [15, 2, 36] which does contain the string 5, 2, 3 so it is just for special cases.

Since you have a dictionary, maybe list comprehension on the keys and string matching? It is actually the same speed as walking through the elements, according to timeit...

s_list = [5,2,3]   # sequence to search for

# Setting up your dictionary
MyD = {'DOC3187' : [1, 2, 3, 6, 7],
    'DOC4552' : [5, 2, 3, 6],
    'DOC4974' : [1, 2, 3, 6],
    'DOC8365' : [1, 2, 3, 5, 6, 7],
    'DOC3738' : [1, 4, 2, 3, 6],
    'DOC5311' : [1, 5, 2, 3, 6, 7]}

query = str(s_list)[1:-1]  # make a string of '5, 2, 3'    
Matches = [ k for k in MyD if query in str(MyD[k]) ]

Result:

['DOC5311', 'DOC4552']

Answer 2

for any sequence 'seq' and longer sequence in your dictionary, 'myseq' the statement:

any(myseq[a:a+len(seq)] == seq for a in range(len(myseq)))

will evaluate to True if seq is a subsequence of myseq, False otherwise

Answer 3

You can use this function:

def find_key_in_dict(d, t):
    """ d is dict for searching, t is target list.
    -> return matching key list.
    """
    b_str = reduce(lambda x, y: str(x) + str(y), t)
    return map(lambda x: x[0], filter(lambda i: b_str in reduce(lambda x, y: str(x) + str(y), i[1]), d.items()))

To search the value, you can use reduce() function to change dict value (integer list) and target list (also integer list) to string, then use 'in' to judge whether the dict value is meet.