[問題案] Permutation Tree

[hotman78]

問題ID: permutation_tree
問題名: Permutation Tree

想定アルゴリズム: Permutation Tree
参考資料: https://codeforces.com/blog/entry/78898

問題概要

Permutation Treeのnodeを出力する
(Permutation Treeの説明を英語できちんとかける気がしない...)

入力

(長さNの順列)

出力

Permutation Treeのnodeを出力する
DFS順preorderで出力(？)
出力形式要検討

制約

1<=N<=5*10^5(10^5 )

[noshi91]

参考 (permutation tree という語の使用を否定するものではありません)

• [1] Uno, T., & Yagiura, M. (2000). Fast algorithms to enumerate all common intervals of two permutations. Algorithmica, 26(2), 290-309.
• [2] Xuan, B. M. B., Habib, M., & Paul, C. (2005, December). Revisiting T. Uno and M. Yagiura’s algorithm. In International Symposium on Algorithms and Computation (pp. 146-155). Springer, Berlin, Heidelberg.
• [3] Common intervals MPRI 2015–2016 https://www.irif.fr/~habib/Documents/CoursMPRI15.pdf

[1] は common interval (2 つの順列があって、それぞれの区間であって出現する数集合が一致するもの) に関する研究です。片方の順列を id としても一般性を失わず、その場合 permutation tree と同じ問題設定になります。
[2] は common interval 全体が木構造で表現できることを指摘して、その木構造 (permutaiton tree のことです) を構築する線形時間のアルゴリズムを説明しています。この木を common interval decomposition tree と定義しています。
[3] は [2] の著者の一人によるスライドですが、tree decomposition of the permutation という語の使用が見られます。

[noshi91]

追記
片方を id として一般性を失わないと書きましたが、その他方の順列のみに着目した場合、connected interval という語も使われているようです。([4] の 4 章)

• [4] Belghiti, I., & Habib, M. (2013). A general method for common intervals. arXiv preprint arXiv:1309.7141.

[noshi91]

[2] では、join は linear、cut は prime と呼ばれています。
[3], [4] では linear をさらに increasing と decreasing の 2 つに分類しています。

[yosupo06]

そもそもpermutation treeの厳密な定義がわからなかったので学習しています　現状以下のような理解なのですが、間違っていたら指摘していただけるとありがたいです。

---

順列の要素の部分集合について、(非空 & 連続 & max - min = R - L)なものの性質について考えている。permutation treeとはこれらからなる集合族(部分集合の集合)を表す木表現。

permutation treeの各ノードは3つの要素を持つ

• node type: cut or join
• Fの要素W
• (そのノードの表す)Fの部分集合Q

ここで、Wに注目するといい感じの木表現になっている。つまり、

• ノードのWは子のWの和集合になっている。また、子のW同士が共通の要素を持つことはない
• 根のWは順列全体
• 葉のWはすべてサイズ1

そして、QはWに含まれるFの要素全体になっている上に、次の条件を満たす

• cut node: QはW + 子のQの和集合
• join node: QはWの非空な部分列全体

疑問点:

• weakly partitive familyな集合族は木で表現できることが知られている(https://www.sciencedirect.com/science/article/pii/S0195669811001806 Theorem 2)？permutation treeはこれを適用しただけ？

• permutation treeは一意？

[noshi91]

私の理解を書いておきます。

---

P を順列とする。connected interval とは、区間 [l, r] であって {P_i | l ≤ i ≤ r} もまた区間となるものである。connected interval のうち、他の connected interval と overlap (非交でも包含でもないこと) しないものを strong であると呼ぶことにする。strong な connected interval 全体は当然互いに overlap しない。よって、strong な区間たちの包含による半順序についてのハッセ図を考えると、[0, N-1] を根、[i, i] を葉とする根付き木になる。これが common interval decomposition tree である。

common interval decomposition tree のノードは linear と prime に分類される。

• linear: 子の列を考えた時、どの連続部分列 (子は自然な順序に並んでいるとして) も connected interval となる
• prime: linear でない

重要な事実: strong でない connected interval は、linear node から導かれるもので全てである。従って、common interval decomposition tree は connected interval 全体の成す構造を完全に表現している。

---

• join node: QはWの非空な部分列全体

「Qは子の非空な部分列が誘導するもの + 子のQの和集合」が正しいと思います。

weakly partitive familyな集合族は木で表現できることが知られている(https://www.sciencedirect.com/science/article/pii/S0195669811001806 Theorem 2)？permutation treeはこれを適用しただけ？

そうだと思っています。

permutation treeは一意？

• 子の個数が 1 のノードをいくらでも挟める
• 子の個数が 2 以下のノードは cut と join が区別できない

これらを除くと一意だと思います。
証明: strong な区間が W と完全に対応することから従う。