0
$\begingroup$

Let's say we've got $n$ numbers to multiply together. But the multiplication operation, like in computer floating-point arithmetics, is not associative. Thus the order of multiplication matters.

Furthermore let's say that we want to minimize the nesting of the expression tree that represents the entire multiplication, so the expression/multiplication tree is the minimum-height binary tree with $n$ leaves.

We want to iterate through all possible ways to multiply the $n$ numbers together.

A way to do it would be to iterate through all permutations of the $n$ numbers (each number is given a position as a leaf of a binary tree), but that would be wasteful, as it would take no advantage of the commutativity property that does hold for this multiplication operation.

Example, $n = 3$: let's call our three numbers $n_1$, $n_2$, $n_3$. There are $3! = 6$ permutations of these three numbers:

123
132
213
231
312
321

The above permutations correspond to these multiplication expressions: $$ (n_1 n_2)n_3 $$ $$ (n_1 n_3)n_2 $$ $$ (n_2 n_1)n_3 $$ $$ (n_2 n_3)n_1 $$ $$ (n_3 n_1)n_2 $$ $$ (n_3 n_2)n_1 $$

However, there are only three equivalence classes when we account for commutativity of the multiplication operation: $$ (n_1 n_2)n_3 = (n_2 n_1)n_3 $$ $$ (n_2 n_3)n_1 = (n_3 n_2)n_1 $$ $$ (n_1 n_3)n_2 = (n_3 n_1)n_2 $$

The goal is to iterate through at least one member of each equivalence class relatively efficiently (better than factorial time), with as little redundancy as possible. So with $n = 3$ we'd ideally iterate through only three permutations, e.g.:

123
132
231

As for the binary trees mentioned above, consider, for example, $n = 4$: we're only interested in expressions with minimal nesting, so $(n_1 n_2)(n_3 n_4)$ is OK, but $((n_1 n_2)n_3)n_4$ isn't, we do not want to iterate through an expression with non-minimal nesting.

In case someone is interested in the motivation for this question, see here: https://math.stackexchange.com/questions/4611399/numerically-stable-evaluation-of-factored-univariate-real-polynomial

To sum up, the goal is to iterate through all equivalence classes of multiplication expressions with minimal nesting, and to do it as efficiently as possible, i.e., I hope I can avoid generating all permutations.

Improve this question
$\endgroup$
11
  • 1
    $\begingroup$ I believe there are exponentially many equivalence classes, so there is no hope to iterate through all of them efficiently. So can you clarify what you are hoping for? Or does that answer your question? $\endgroup$
    – D.W. ♦
    Jan 25 at 7:02
  • 1
    $\begingroup$ Did I understand correctly that a tree is "balanced" if it has the minimum height? I.e. you don't care if some leaves have a height much less than the tree height. So the tree $(((12) (34)) 5)$ is balanced. $\endgroup$
    – Dmitry
    Jan 25 at 7:17
  • 1
    $\begingroup$ Anyway, the idea is to look at the last multiplication (i.e. at the root of the tree). You want to partition the entire set of multipliers into two sets, and run recursively on these sets. E.g., for $3$ elements there are only $3$ possible partitions: $\{1,2\} \cup \{3\}$, $\{1,3\} \cup \{2\}$, $\{1\} \cup \{2,3\}$, corresponding to the three multiplication orders you specified. The only non-trivial part is to consider only partitions such that it's possible to build the balanced subtrees (whatever "balanced" means), but it's easy to address (by just looking at the cardinalities of the sets). $\endgroup$
    – Dmitry
    Jan 25 at 7:24
  • $\begingroup$ @Dmitry, sorry I used binary tree terminology incorrectly, I edited the question. $\endgroup$
    – user2373145
    Jan 25 at 12:49
  • $\begingroup$ @D.W. sorry, I'm interested in some relatively good time complexity, in particular I'm interested in whether there's a sub-factorial algorithm. Dmitry may have answered that in his comment, which I will now review. $\endgroup$
    – user2373145
    Jan 25 at 12:54

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.