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