The code is supposed to produce a two dimensional list of all the possible ways a target can be reached from a list of word bank but the actual output confuses me. Is there a better way to tackle this problem?
def all_construct(target, word_bank):
table = [[]] * (len(target) + 1)
table[0] = [[]]
for i in range(len(target)+1):
for word in word_bank:
word_len = len(word)
if target[i:(i +word_len)] == word:
combination_list = list(map(lambda sub_list: [*sub_list, word], table[i]))
#combination_list = [[*sub_list, word] for sub_list in table[i]]
table[i + word_len].extend(combination_list)
return table[i]
print(all_construct("abcdef", ["ab", "abc", "cd", "def", "abcd", "ef", "c"]))
Your code isn't working, and it raises SyntaxError, because the second for loop isn't indented, codeblocks need to be indented. After fixing the indentation error your code still doesn't work.
That being said, I have abandoned the idea to fix your code. I have wrote two working implementations that produce the correct output. One bruteforce method and one smart method.
The bruteforce method is simple, first we choose all possible subsets of n elements for all n up to length, and get all permutations of the subsets and check if the permutations add up to the target.
To choose n elements from a total of m elements, each element can be chosen or not chosen, there are only two possibilities, and exactly n elements will be chosen, n cannot be greater than m. There are a total of 2m ways to choose combinations of n elements.
This is powerset. We can use binary numbers to choose the elements from the list, for all numbers from 0 to 2m - 1, get the binary representation of the number and select an element if the digit at the corresponding index is 1:
def powerset(s):
l = len(s)
return [[a for a, b in zip(s, bin(i)[2:].zfill(l)) if b == '1'] for i in range((1 << l))]
To get all permutations, we choose n elements in order, we can choose n elements to be the first, after that we can only choose n - 1 elements to be the second, there are n - 2 elements that can be the third... And the last can only be one possibility. There are n! ways to arrange n elements.
We can use a recursive function to recursively choose nth element as the first:
def permutation(ls):
if not ls:
return []
if len(ls) == 1:
return [ls]
result = []
for i, e in enumerate(ls):
result.extend([e] + p for p in permutation(ls[:i] + ls[i+1:]))
return result
Putting it together, the code becomes:
def powerset(s):
l = len(s)
return [[a for a, b in zip(s, bin(i)[2:].zfill(l)) if b == '1'] for i in range((1 << l))]
def permutation(ls):
if not ls:
return []
if len(ls) == 1:
return [ls]
result = []
for i, e in enumerate(ls):
result.extend([e] + p for p in permutation(ls[:i] + ls[i+1:]))
return result
def all_construct(target, word_bank):
return [perm for subset in powerset(word_bank) for perm in permutation(subset) if ''.join(perm) == target]
The above method is extremely inefficient.
Instead of making permutations and checking them, we can split the target string into component parts, more specifically we can just split the string into substrings of difference lengths that add up to the string, we are partitioning the string and there are 2n - 1 ways to partition a string of length n. Then we can check if all substrings are in the wordbank and appearing no more times than they appear in the wordbank.
To partition a string, we recursively choose n first characters and choose n characters from the rest of the string for all possible n, until there is no string left.
def substring_tree(s: str) -> dict:
d = {}
def worker(s: str, dic: dict):
for i in range(1, len(s) + 1):
dic[s[:i]] = {}
worker(s[i:], dic[s[:i]])
worker(s, d)
return d
Putting it all together:
from collections import Counter
def substring_tree(s: str) -> dict:
d = {}
def worker(s: str, dic: dict):
for i in range(1, len(s) + 1):
dic[s[:i]] = {}
worker(s[i:], dic[s[:i]])
worker(s, d)
return d
def traverse_tree(tree, wordbank, keys, substrings=list()):
result = []
for k, v in tree.items():
if k in wordbank and keys[k] < wordbank[k]:
keys = keys.copy()
keys[k] += 1
if v:
result.extend(traverse_tree(v, wordbank, keys, substrings + [k]))
else:
result.append(substrings + [k])
return result
def all_construct2(target, wordbank):
wordbank = Counter(wordbank)
return traverse_tree(substring_tree(target), wordbank, Counter())
Output:
In [58]: all_construct("abcdef", ["ab", "abc", "cd", "def", "abcd", "ef", "c"])
Out[58]: [['abcd', 'ef'], ['abc', 'def'], ['ab', 'c', 'def'], ['ab', 'cd', 'ef']]
In [59]: all_construct2("abcdef", ["ab", "abc", "cd", "def", "abcd", "ef", "c"])
Out[59]: [['ab', 'c', 'def'], ['ab', 'cd', 'ef'], ['abc', 'def'], ['abcd', 'ef']]
Performance:
In [60]: %timeit all_construct("abcdef", ["ab", "abc", "cd", "def", "abcd", "ef", "c"])
40.4 ms ± 1.11 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)
In [61]: %timeit all_construct2("abcdef", ["ab", "abc", "cd", "def", "abcd", "ef", "c"])
73.6 µs ± 1.35 µs per loop (mean ± std. dev. of 7 runs, 10,000 loops each)