「木構造と自然数の重複あり集合は等価だよね」というはなし - EchizenBlog-Zwei

「木構造と自然数の重複あり集合は等価だよね」というはなしをする。簡潔データ構造な人向けに言うとLOUDSの話。 とはいえこの記事は特に簡潔データ構造の知識を要求しない。データ構造とか情報量とかに興味がある人全般を対象としている。 ※簡潔勢にとっては既知な話のはずなのであえて読む必要はないです。 まず結論から述べる。以下のような幅優先で番号を振った木構造を考える。 親 → 子 (1) → (2, 3) (2) → (4) (3) → (5)この木構造は以下の重複あり集合によって表現することができる。 { 2, 4, 5, 5, 5 }これだけ書くとなんのこと？と思われるかもしれない。そこでこれから2つのことを説明する。ひとつは「何故、木構造が自然数の重複あり集合で表現できるか」、もうひとつは「重複あり集合で表現することに何の意味があるか」ということ。 何故、木構造が自然数の重複あり集合で表現

[keijak]

LOUDS の中身について。簡潔データ構造おもしろいなー。

[yowa]

Prüfer Code の話かと思ったら違った | http://mathworld.wolfram.com/PrueferCode.html

[pmint]

"普通に考えると"の件にある「扱うのはインデックスだけ」という点を最初に読みたかった。順序は必要、でもそれは別に控えておいてここでは考えない。あとはランダムアクセスを捨てれば情報量が最適になるという話。

[usurausura]

幅優先でノードに連番をふった木構造と、自然数の重複あり集合の対応。「意外な対応」繋がりで思わずこの本を思い出した：整数の分割http://www.sugakushobo.co.jp/903342_61_mae.html http://mathsoc.jp/publication/tushin/1502/1502mizuno.pdf

[msykt]

面白いー

[akira_108]

すごい！

[tmatsuu]

ほう

[als_uz]

一瞬よくわからなかったけど読み直したらよくわかった。こういうの考えられる人すごいなーと思う

[yojik]

“LOUDS”