Upper bounds for expression tree search space sizes

Description

These functions return the number of structurally different expressions or expression shapes of a given depth or size that can be build from a fixed function- and input-variable set. Here, "expression shape" means the shape of an expression tree, not taking any node labels into account. exprShapesOfDepth returns the number of structurally different expression shapes of a depth exactly equal to n. exprShapesOfMaxDepth returns the number of structurally different expression shapes of a depth less or equal to n. exprsOfDepth returns the number of structurally different expressions of a depth exactly equal to n. Note that constants are handled by conceptually substiting them with a fresh input variable. exprShapesOfMaxDepth returns the number of structurally different expressions of a depth less or equal to n. Note that constants are handled by conceptually substiting them with a fresh input variable. exprShapesOfSize, exprShapesOfMaxSize, exprsOfSize, exprsOfMaxSize are equivalents that regard expression tree size (number of nodes) instead of expression tree depth.

Usage

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
exprShapesOfDepth(funcset, n)

exprShapesOfMaxDepth(funcset, n)

exprsOfDepth(funcset, inset, n)

exprsOfMaxDepth(funcset, inset, n)

exprShapesOfSize(funcset, n)

exprShapesOfMaxSize(funcset, n)

exprsOfSize(funcset, inset, n)

exprsOfMaxSize(funcset, inset, n)

Arguments

funcset

The function set.

inset

The set of input variables.

n

The fixed size or depth.

Want to suggest features or report bugs for rdrr.io? Use the GitHub issue tracker.