Advertisement
Guest User

Untitled

a guest
Jun 14th, 2012
111
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 0.89 KB | None | 0 0
  1. def possible_nexts(word, chunks):
  2.     result = []
  3.     for chunk in chunks:
  4.         if word.startswith(chunk): result.append(chunk)
  5.     return result
  6.  
  7. def generate_tree(word, chunks):
  8.     result = []
  9.     nexts = possible_nexts(word, chunks)
  10.     for next in nexts:
  11.         current = [next]
  12.         current.extend(generate_tree(word[len(next):], chunks))
  13.         result.append(current)
  14.     if not nexts:
  15.         if word: return [[False]]
  16.     return result
  17.  
  18. def is_valid(tree):
  19.     value, *children = tree
  20.     if value is False: return False
  21.     elif not children: return True
  22.     else: return any([is_valid(child) for child in children])
  23.  
  24. def filter_valid(tree):
  25.     value, *children = tree
  26.     return [value] + list(map(filter_valid, [child for child in children if is_valid(child)]))
  27.  
  28. def to_tree(word, chunks):
  29.     return filter_valid([word] + generate_tree(word, list(set(chunks))))
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement