Revision history [back]

The trick is probably to define correctly what is a leaf. First rough attempt :

def LC(x):
    def is_leaf(x):
        from sage.symbolic.expression import Expression
        return type(x) is not Expression or x.is_symbol() or x.is_numeric()
    if is_leaf(x): return 1
    return sum(map(LC, x.operands()))
sage: LC(sin(a+b))
2
sage: LC(sin(a+b).trig_expand())
4
sage: LC(integrate(sin(x), x, a, b, hold=True))
4

Note that, by design, it won't work on anything else than a symbolic expression ; polynomials, rational fractions, series, etc..., here considered as a leaf, need their own implementation, whose definition of "leaf" isn't a trivial question. Consider :

sage: R1.<t>=QQ[]
sage: LC(t^3-3*t^2+t-1)
1
sage: LC(SR(t^3-3*t^2+t-1))
7
sage: len((t^3-3*t^2+t-1).coefficients())
4
sage: len((t^3).coefficients())
1

Anyway, this is probably not sufficiently "general" to deserve an implementation in "core" Sage. A package grouping some tree-related utilities could be considered...

BTW, the "complexity" of an expression isn't only a function of the number of its leaves, but also of the number of itsnon-terminal nodes, the distribution of the depth of its branches and the structure of common subexpressions... AFAIK, there is no universally acknowledged metric of an expression's "complexity"...

HTH,

The trick is probably to define correctly what is a leaf. First rough attempt :

def LC(x):
    def is_leaf(x):
        from sage.symbolic.expression import Expression
        return type(x) is not Expression or x.is_symbol() or x.is_numeric()
    if is_leaf(x): return 1
    return sum(map(LC, x.operands()))
sage: LC(sin(a+b))
2
sage: LC(sin(a+b).trig_expand())
4
sage: LC(integrate(sin(x), x, a, b, hold=True))
4

Note that, by design, it won't work on anything else than a symbolic expression ; polynomials, rational fractions, series, etc..., here considered as a leaf, need their own implementation, whose definition of "leaf" isn't a trivial question. Consider :

sage: R1.<t>=QQ[]
sage: LC(t^3-3*t^2+t-1)
1
sage: LC(SR(t^3-3*t^2+t-1))
7
sage: len((t^3-3*t^2+t-1).coefficients())
4
sage: len((t^3).coefficients())
1
sage: len((t^3).coefficients(sparse=False))
4

Anyway, this is probably not sufficiently "general" to deserve an implementation in "core" Sage. A package grouping some tree-related utilities could be considered...

BTW, the "complexity" of an expression isn't only a function of the number of its leaves, but also of the number of itsnon-terminal its non-terminal nodes, the distribution of the depth of its branches and the structure of common subexpressions... AFAIK, there is no universally acknowledged metric of an expression's "complexity"...

HTH,