I’ve been struggling with this for a few days, and so I thought I might ask this here. Part of the problem lies in the fact that I do not even know the mathematical solution, which runs the risk of this question falling out of the scope of this site. Nevertheless, I’ll proceed:
Consider this unexpanded polynomial of Symbols constructed out of heads Plus and Times only:
poly = ((a + b) (c + d (e + f)) + (g + h) i) j + k
What I’d like to do: Without expanding the polynomial, mark the leaves of the polynomial by integers based on its position in the tree. This labeling of leaves must have the property such that
- When
Expanded, each factor in each term is given a unique label - No more labels are used than necessary for the whole polynomial (number of distinct labels equals overall order of polynomial in all its variables).
For poly, a solution is
((a[1] + b[1]) (c[2] + d[2] (e[3] + f[3])) + (g[2] + h[2]) i[1]) j[0] + k[0]
The result is not unique, but observe that the expanded form satisfies both requirements 1 and 2.
a[1] c[2] j[0] + b[1] c[2] j[0] + a[1] d[2] e[3] j[0] +
b[1] d[2] e[3] j[0] + a[1] d[2] f[3] j[0] + b[1] d[2] f[3] j[0] +
g[2] i[1] j[0] + h[2] i[1] j[0] + k[0]
It is not necessary that terms with fewer factors use specific labels in any order: for example a labeling of the polynomial in which the 2nd last term of the expanded form is h[1] i[3] j[0] (missing label 2) or in which the last term is k[2] is acceptable.
Moreover I’d like a solution that is faster than just expanding the polynomial and labeling each term.
My original attempt was based on traversing the tree,
and raising/lowering the value of the label based on whether it passes through Plus or Times. Unfortunately, none of my solutions based on this give the correct answer.
