getTrees = {
// Generate all trees with exactly nodeCount nodes and leafCount leaves, using the cache
// for the subproblems.
function *getTrees(nodeCount, leafCount, maxIndex = Infinity) {
if (nodeCount === 1) {
if (leafCount === 1) {
yield { tree: 1, index: 0 };
}
} else {
let i = 0;
for (const children of remainingChildren(nodeCount - 1, leafCount)) {
if (i > maxIndex) break;
yield { tree: children, index: i++ };
}
}
}
function *remainingChildren(nodesLeft, leavesLeft, [prevNodeCount, prevLeafCount, prevIndex] = [0, 0, 0]) {
if (nodesLeft === 0 && leavesLeft === 0) {
yield [];
return;
}
if (nodesLeft < leavesLeft) {
return;
}
// only generate further children with:
// - non-decreasing node count;
// - same node count and non-decreasing leaf count; or
// - same node and leaf count but non-increasing tree index
// note: the third case only becomes important when leavesLeft >= 4
const minNodeCount = prevNodeCount || 1;
for (let nodeCount = minNodeCount; nodeCount <= nodesLeft; nodeCount++) {
const minLeafCount = nodeCount === prevNodeCount ? prevLeafCount : 1;
for (let leafCount = minLeafCount; leafCount <= leavesLeft; leafCount++) {
if (leavesLeft === leafCount && nodesLeft > nodeCount) continue; // this line is new
const trees = (nodeCount === prevNodeCount && leafCount === prevLeafCount) ?
getTrees(nodeCount, leafCount, prevIndex) : getTrees(nodeCount, leafCount);
for (const { tree, index } of trees) {
for (const rest of remainingChildren(
nodesLeft - nodeCount,
leavesLeft - leafCount,
[nodeCount, leafCount, index])) {
yield [tree, ...rest];
}
}
}
}
}
return getTrees;
}
{
const N = 30;
const M = 3;
const treeCounts = {};
for (let m = 1; m <= M; m++) {
treeCounts[m] = 0;
for (const {tree, index} of getTrees(N, m)) {
treeCounts[m]++;
console.log(N, m, index, JSON.stringify(tree))
}
}
return treeCounts;
}
Purpose-built for displays of data
Observable is your go-to platform for exploring data and creating expressive data visualizations. Use reactive JavaScript notebooks for prototyping and a collaborative canvas for visual data exploration and dashboard creation.
