Check if list is composed by other lists

Question

I want to find out which items of the list m are entirely composed of items of list w.

If i add them into sets and make an intercept, the embedded structure becomes invisible, which is exactly what i want to avoid.

Case:

w= [
     ['sta'], 
     ['co', 'si'], 
     ['non'], 
     ['si'], 
     ['puo'], 
     ['ap', 'ri', 're'], 
     ['ve', 'dia', 'mo'], 
     ['co', 'sa'], 
     ['ci'], 
     ['pot', 'reb', 'be']
   ]

m=[
     ['sta', 'co'], 
     ['puo', 'ap', 'ri', 're'], 
     ['ve'], 
     ['dia', 'mo'], 
     ['co'], 
     ['sa'], 
     ['ci', 'pot', 'reb', 'be']
  ]

Desired output:

[['puo', 'ap', 'ri', 're'], ['ci', 'pot', 'reb', 'be']]

(e.g. ['puo', 'ap', 'ri', 're'] from m is composed of two items from w: [['puo'], ['ap', 'ri', 're']]).

Thanks you all!

Answer 1

The algoithm for each element "elem" of the list "list" checks recursively if (the list elem[1:] and the list elem[:1]) or (the list elem[2:] and elem[:2]) or ... are composed by elements contained in the list w. I also use the map "memory" to optimize the algorithm using the memoization technique.

def listInList(a, list, memory):
    if not list:
        return False
    elif str(list) in memory:
        return memory[str(list)]
    else:
        if list in a:
            memory[str(list)] = True
            return True
        else:
            for i in range(1,len(list)):
                if listInList(a, list[i:], memory) and listInList(a, list[:i], memory):
                    memory[str(list)] = True
                    return True
            memory[str(list)] = False
            return False

def check(a, b):
    res = []
    for elem in b:
        if listInList(a, elem, {}):
            res += [elem]
    return res

w= [
     ['sta'],
     ['co', 'si'],
     ['non'],
     ['si'],
     ['puo'],
     ['ap', 'ri', 're'],
     ['ve', 'dia', 'mo'],
     ['co', 'sa'],
     ['ci'],
     ['pot', 'reb', 'be']
   ]
m=[
     ['sta', 'co'],
     ['puo', 'ap', 'ri', 're'],
     ['ve'],
     ['dia', 'mo'],
     ['co'],
     ['sa'],
     ['ci', 'pot', 'reb', 'be']
  ]
print check(w,m)

Output:

[['puo', 'ap', 'ri', 're'], ['ci', 'pot', 'reb', 'be']]