bonotakeの日記

元・ソフトウェア工学系研究者、今・AI系エンジニア

Seven trees 解答編:圧縮方法

さて、圧縮方法について触れる前に、id:ku-ma-meさんのところにある、T→T7までの18ステップをこちらにも載せておきます。ついでに表にしてみました。

T0 T1 T2 T3 T4 T5 T6 T7 T8
0: 0 1 0 0 0 0 0 0 0
1: 1 0 1 0 0 0 0 0 0
2: 1 1 0 1 0 0 0 0 0
3: 1 1 1 0 1 0 0 0 0
4: 1 1 1 1 0 1 0 0 0
5: 1 1 1 1 1 0 1 0 0
6: 1 1 1 1 1 1 0 1 0
7: 1 1 1 1 1 1 1 0 1
8: 1 1 1 1 1 2 0 1 1
9: 1 1 1 1 2 1 1 1 1
10: 1 1 0 2 1 1 1 1 1
11: 1 0 1 1 1 1 1 1 1
12: 0 1 0 1 1 1 1 1 1
13: 0 0 1 0 1 1 1 1 1
14: 0 0 0 1 0 1 1 1 1
15: 0 0 0 0 1 0 1 1 1
16: 0 0 0 0 0 1 0 1 1
17: 0 0 0 0 0 0 1 0 1
18: 0 0 0 0 0 0 0 1 0

左端のカラムが行番号(0が初期状態)、他はそれぞれTiの係数を表しています。
表中の赤字が 展開 Tn→Tn-1+Tn+1 を適用している箇所、青字が縮約 Tn-1+Tn+1 → Tn を適用している箇所です。
これを上から下へ順に辿ると g:T7 → T、下から上へ遡ると f:T → T7 が完成するわけですが*1。見てのとおり、fとgは非常に対称的になっています。実際、この表の真ん中(9ステップめの、T4のところ)を中心にくるっと180°回転すると、Tの次数の並びが逆になるだけで、展開・縮約の適用順と並びは全く同じになります。この相似性からして、TとT7の間にはただならぬ関係があるのではないか、という気になります。


で、圧縮にはこの対称性を利用…しませんでした。まったく。いひ。


ということで、続きは後で。…と思って今せこせこ書いてたんですが、手違いで一気に消えちゃいました。がっくし。なので気力回復したら書きます。

とりあえずざっと注記しておきますと、ステップ9までのひたすら展開(=場合分け)をし終わった時点で、取り得るパターンが10通り(T0からT8までの各係数を足した合計)分存在します。
この10通りは、残りのステップで縮約しても根本的には消えないのです。あとは細かい式の解釈とパターンマッチの書き方の問題で、ゴルフ的労力の問題になります。自分は1分岐減らせただけになりました。

なので5分岐にするには、元の式変形から変える必要があるんじゃないかなーと思ってますが、どうなんでしょう。他の人の解答まだ見てないので、もしかしたら嘘かもしれませんが。

[追記] と考えてふと、別の式変形でやってみました。ヒビルテの解答を参考にして、後半をちょっと修正したら、結果として展開9回、縮約9回の合計18ステップで同じになりました(適用順は全然違うけど)。でも、これでも結局、展開(=場合分け)を9回やれば、やっぱりパターンの数は10通りで変わりませんね。やっぱり後は、この10通りの並べ方の問題か。んー。
ちなみに、これ。

T0 T1 T2 T3 T4 T5 T6 T7 T8
0: 0 1 0 0 0 0 0 0 0
1: 1 0 1 0 0 0 0 0 0
2: 1 1 0 1 0 0 0 0 0
3: 1 1 1 0 1 0 0 0 0
4: 0 2 0 0 1 0 0 0 0
5: 0 2 0 1 0 1 0 0 0
6: 0 1 1 0 0 1 0 0 0
7: 0 1 1 0 1 0 1 0 0
8: 0 1 0 1 0 0 1 0 0
9: 0 1 0 1 0 1 0 1 0
10: 0 0 1 0 0 1 0 1 0
11: 0 0 1 0 1 0 1 1 0
12: 0 0 0 1 0 0 1 1 0
13: 0 0 0 1 0 1 0 2 0
14: 0 0 0 0 1 0 0 2 0
15: 0 0 0 0 1 0 1 1 1
16: 0 0 0 0 0 1 0 1 1
17: 0 0 0 0 0 0 1 0 1
18: 0 0 0 0 0 0 0 1 0

これはこれで、対称な変形になってますね。

*1:これを実直にコードにしたのがku-ma-meさんの解答

注:bonotakeは、amazon.co.jpを宣伝しリンクすることによってサイトが紹介料を獲得できる手段を提供することを目的に設定されたアフィリエイト宣伝プログラムである、 Amazonアソシエイト・プログラムの参加者です。