読者です 読者をやめる 読者になる 読者になる

差分リストによる入れ子リストの平坦化

久しぶりにアルゴリズムが理解できずに詰みかけたので、メモ。


差分リストを用いて、入れ子リストを平坦化(入れ子をなくす)アルゴリズム

1.nilの平坦化はX#X(空の差分リスト)

2.Xを入れ子のリストとして、X|Xrを平坦化するとY1#Y4。
 ただし、Xの平坦化はY1#Y2
     Xrの平坦化はY3#Y4
 で差分リストを連結するためにY2=Y3となるようにする。

3.Xがリストでないとして、X|Xrを平坦化すると(X|Y1)#Y2になる。ここでXrの平坦化はY1#Y2.

4.Xを入れ子リストとして、X|Xrを平坦化するとY1#Y4になる。
 ここで、Xの平坦化はY1#Y2
     Xrの平坦化はY2#Y4


となっている。
そこで簡単のため、X|Xr=[[a b] [c d]]とすると

X=[a b]、Xr=[c d]なので、2.(4.)の操作を行い

X → Y1#Y2 (Y1 = [a b c d X]、Y2 = [c d X])
Xr→ Y2#Y4 (Y4 = X)

となる。
これから、Y1#Y4 = [a b c d X]#X となって[a b c d]となり、確かにX|Xrの平坦化された結果となっている。
他の場合もこのように考えると、この繰り返しで平坦化できることが分かる。

広告を非表示にする