I have this problem:
Let $S$ be a set which is the domain with two operators $+$ and $*$ and an element $0$ such that:
$+$ is a binary operator that is:
- associative
- commutative
- idempotent (that is, $x + x = x$ for all $x \in S$)
- $x + 0 = 0 + x = x$ for all $x \in S$
$*$ is a binary operator that is:
non-associative
non-commutative
- $x * 0 = 0 * x = 0$ for all $x \in S$
The operators $+$ and $*$ satisfy the distributive laws: That is,for all $x,y,z \in S$,
- $ x * (y + z) = x*y + x*z$
- $ (y + z) * x = y*x + z*x$
Given $n$ elements $x_1, x_2, \cdots , x_n$ from $S$ describe an algorithm to compute the sum of products of $x_1, x_2, \cdots , x_n$ in this order, under all possible groupings for the products.
For example, if $n = 3$, it is required to compute $ (x_1 * (x_2 * x_3)) + ((x_1 * x_2) * x_3) $
It looks similar to Matrix Chain Multiplication at first, but since it's using all groupings, not just an optimal one, I figured that wouldn't work here. My next thought was that there would only be $n^3$ ways to multiply $n$ numbers together, but that doesn't account for groupings like $(x_1*x_2)(x_3*x_4)$. I'm pretty lost on this now though, can someone point me in the right direction?