右ノードでのツリーの起動

バックグラウンド

ルーテッドツリーは、1つのパスから正確に1つのパスがあるような非循環グラフですノードと呼ばれ、ルートと呼ばれます。
rootから u へのパスが存在する場合に限り、 v ノードは別のノード
uv を通り、 u
v を結ぶエッジがあります。ノード v がノード u
の親である場合、ノード u
はノード/code>

仕事

正の整数のノードと各親が持つ負でない整数の集合を与え、その数のノード(ルートを含む)と各頂点が持つ可能なルート木の数を出力するプログラムまたは関数を記述するすでに見つかったツリーにそのツリーを数えずに、セット内のいくつかの子供が同形になります。

2つのツリーは、ノードの名前を変更して別のツリーに変換できる場合、つまりノードのラベルが付けられていない場合は同じものを表示する場合、同形です。

[[1]、[2]、[]] はルートが 0
であることを表します。/code>は子として 1 を持ち、ノード 1
は子としてノード 2 を持ち、ノード 2
子供はいない。

n = 3 とset = [0,1,2]
を入力します。これは、3つのノードを持つバイナリツリーに相当します。 考えられる2つのツリーは
[[1]、[2]、[]][[1,2]、[]、[]] です。
2つのツリーの構造は同じであるため、 [[2]、[]、[1]]
[[2,1]、[]、[]] 。 2つのツリーがあるので、出力は 2
または同等です。

視覚化は次のとおりです: 最初の例のビジュアライゼーション
2つ目のツリーの2つ目のセットは、最初の2つのセットと同じ構造であるため、カウントされません。両方のセットは、次の2つの構造のうちの1つを持つ2つのツリーで構成されています(ルートは最上位のノードです)。

Visualization for symmetry group of first example


n = 5 とset = [0,2] を入力します。可能なツリーは
[[1,2]、[3,4]、[]、[]、[]] です。例えば、
[1,2]、[]、[3,4]、[]、[]] および [[1,3]、[]、
]、[2,4]、[]]
は、カウントされる単独のツリーと同形であるため、再度カウントされません。出力は
1 または同等です。

もう一つの可視化があります:

Visualization for example 2 Clearly, all of the trees are
isomorphic, so only one is counted. Here is what the trees look
like unlabeled:

enter image description here


n = 4 、set = [0,2]
を入力します。子ノードがノードから生成されるたびに、 0 または 2
以上のノードが存在するため、ツリーが存在しません。明らかに、 2 または 0
をルートである 1 ノードに続けて追加することで、4つのノードを生成することはできません。出力:
0 またはfalseです。

入出力

入力と出力は、合理的なフォーマットで行う必要があります。

入力は、 n
を表す正の整数と、子の有効な数値の集合を表す負でない整数のリストです。

出力は、形成可能なツリーの数に対応する非負の整数です。

テストケース

ルール

  • 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 test case)
  • This is , so shortest code wins.
ベストアンサー

Haskell, 120 bytes

_#0=1
i#j=div(i#(j-1)*(i+j-1))j
s!n|let(0?1)0=1;(0?_)_=0;(m?n)c=sum[s!m#j*((m-1)?(n-j*m)$c-j)|j<-[0..c]]=sum$(n-1)?n<$>s

Try it
online!

使い方

i#j is i multichoose j.

(m?n)c is the number of n-node trees
with c children at the root, each of which has a
subtree of at most m nodes. It’s computed by summation
over j, the number of these subtrees that have exactly
m nodes.

s!n is the number of n-node trees.
It’s computed by summation over cs,
the number of children at the root.

返信を残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です