I'm struggling with an interesting problem from a chapter about Dynamic Programming in Skienas' famous "The Algorithm Design Manual". It's listed on the following web-page under number 8-22: http://www.algorist.com/algowiki/index.php/Divide-TADM2E#8-22
The problem asks you to write a polynomial-time algorithm using DP which solves a special case of the Word Problem over finite groupoids:
Given a finite groupoid $G$, a word $s$ on $G$ and an $x \in G$, find out whether it is possible to parenthesize $s$, such that its evaluation will yield $x$. Example from the book:
\begin{array}{c|ccc} & a & b & c \\ \hline a & a & c & c \\ b & a & a & b \\ c & c & c & c \\ \end{array}For instance, consider the above multiplication table and the string $bbbba$. Parenthesizing it $(b(bb))(ba)$ gives $a$, but $((((bb)b)b)a$ gives $c$.
So far I managed to write a naive $O(n!)$ recursive algorithm in Python:
def i(x):
return ord(x) - ord('a')
def mul(x, y):
return groupoid[i(x)][i(y)]
# rewrite('abc', 1) = 'ac'
# rewrite('abc', 0) = 'cc'
def rewrite(word, i):
return word[:i] + mul(word[i], word[i+1]) + word[i+2:]
def search(word, x):
exists = (word == x)
for i in range(0, len(word) - 1):
if exists:
break
exists |= search(rewrite(word, i), x)
return exists
word = sys.argv[1]
x = sys.argv[2]
exists = search(word, x)
print('Solution exists' if exists else 'Unsolvable')
Although we can memoize search
, it won't give us polynomial time, since memoization space is of a factorial order. This is where I'm stuck.
The problem here is to somehow reduce the factorial search-space of all possible reductions from $s$ on $G$ to a polynomial search-space, which will depend only on $|s|$ and $|G|$. Can you please help me with that? Any other hints?
i
) for two purposes is unnecessarily confusing. Also, we'd generally prefer that you avoid sharing specific Python code and instead provide concise pseudocode that doesn't require knowledge of any particular programming language to understand. $\endgroup$