7
1
Background
A rooted tree is an acyclic graph such that there is exactly one path from one node, called the root, to each other node. A node v
is called the parent of another node u
if and only if the path from the root to u
goes through v
and there is an edge connecting u
and v
. If node v
is the parent of node u
, node u
is a child of node v
.
Task
Write a program or function that, given a positive integer number of nodes and a set of non-negative integer numbers of children each parent has, outputs the number of possible rooted trees with that number of nodes (including the root) and each vertex having a number of children in the set, not counting those trees isomorphic to trees already found.
Two trees are isomorphic if one can be transformed into another by renaming the nodes, or in other words look the same when the nodes are unlabelled.
Examples
We shall represent trees as a 0-indexed list of children per index where 0 represents the root, for example [[1],[2],[]]
represents that the root 0
has 1
as a child, node 1
has node 2
as a child, and node 2
has no children.
Inputs n=3
and set = [0,1,2]
. This is equal to binary trees with three nodes.
The two possible trees are: [[1],[2],[]]
and [[1,2],[],[]]
. Because they are identical in structure to the two trees, we count neither [[2],[],[1]]
nor [[2,1],[],[]]
. There are two trees, so the output is 2
or equivalent.
Here is a visualization: You can see that the second set of two trees are identical in structure to the first set of two and are thus not counted. Both sets are composed of two trees which have one of the following two structures (the root is the node at the top):
Inputs n=5
and set=[0,2]
. The only possible tree is [[1,2],[3,4],[],[],[]]
. Note that, for example, [[1,2],[],[3,4],[],[]]
and [[1,3],[],[],[2,4],[]]
are not counted again because they are isomorphic to the sole tree which is counted. The output is 1
or equivalent.
Here is another visualization:
Clearly, all of the trees are isomorphic, so only one is counted. Here is what the trees look like unlabeled:
Input n=4
, set=[0,2]
. There are no possible trees because each time children are generated from a node, there are either 0
or 2
more nodes. Clearly, 4 nodes cannot be produced by adding 2
or 0
successively to 1
node, the root. Output: 0
or falsey.
Input/Output
Input and output should be taken in a reasonable format.
Input is a positive integer representing n
and a list of non-negative integers representing the set of valid numbers of children.
The output is a non-negative integer corresponding to how many trees can be formed.
Test cases
n ; set ; output
3 ; [0,1,2] ; 2
5 ; [0,2] ; 1
4 ; [0,2] ; 0
3 ; [0,1] ; 1
3 ; [0] ; 0
1 ; [0] ; 1
6 ; [0,2,3] ; 2
7 ; [0,2,3] ; 3
Rules
- The set of numbers of children will always include zero.
- The root node always counts as a node, even if it has no children (see the
1; [0]
test case) - This is code-golf, so shortest code wins.
When you say two trees are isomorphic, you mean as rooted trees, right? – xnor – 2017-06-07T23:47:11.507
@xnor Yes. The isomorphic definition refers to rooted trees. – fireflame241 – 2017-06-07T23:48:58.023