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 `Symbol`

s 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
`Expand`

ed, 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.