How to test membership of sequence in python list?

Question

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.

Also, please show the actual dictionary, not just the contents — thefourtheye, May 13 '14 at 03:27
@thefourtheye: I often encourage users, especially those who are new to Stack Overflow, to copy and paste *actual* code and/or *actual* interactive sessions, to make sure we get an accurate picture. And OP certainly has not done that here. But he or she has stated precisely what's in the dictionary. Keys are strings, values are lists. What do you even mean by "the actual dictionary" if not the contents? Do you need to see it as `{'DOC3187': [1, 2, 3, 6, 7], 'DOC4552': [5, 2, 3, 6],` etc.? — John Y, May 13 '14 at 04:01
@JohnY albeit not necessary, as there is enough information, it is better if one can just copy-paste the dictionary to check the answer. — Davidmh, May 13 '14 at 18:07

Joe Tannenbaum · Answer 1 · 2014-05-13T02:30:30.390

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

edited May 13 '14 at 02:30

answered May 13 '14 at 02:23

Joe Tannenbaum

160
4

score 0 · Answer 2 · answered May 13 '14 at 03:44

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.

beroe · Accepted Answer · 2014-05-13T17:36:38.703

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']

How to test membership of sequence in python list?

3 Answers3