コンテンツにスキップ

0651: same fringe 問題

問題

入れ子タプルで表した木のフリンジ（葉を左から右へ並べた列）を扱います。 タプルは内部節点、タプルでない値は葉とみなします。 例えば ((1, 2), 3) と (1, (2, 3)) は形の異なる木ですが、フリンジはどちらも 1, 2, 3 です。

次の2つの関数を実装してください。

def fringe(tree: Any) -> Iterator[Any]: ...
def same_fringe(t1: Any, t2: Any) -> bool: ...
  • fringe(tree) は木の葉を左から右の順に生成するジェネレータです。再帰と yield from で実装します。
  • same_fringe(t1, t2) は2つの木のフリンジが等しいときに限り True を返します。

この判定は same fringe 問題として知られる古典問題です。 2つの再帰的走査を交互に少しずつ進める必要があることから、コルーチンを説明する例として使われてきました。

制約

  • 木はタプルの入れ子で表します。空タプルは葉を1枚も持たない部分木です。
  • タプルでない値はすべて葉です（木全体が1枚の葉である場合を含みます）。葉の等価性は == で判定します。
  • same_fringe() はフリンジ全体をリストなどに展開してはいけません。走査は遅延させ、判定に必要な葉だけを取り出します。
  • 葉の枚数が異なる場合（一方のフリンジが他方の接頭辞になっている場合を含みます）は False を返します。

例

>>> list(fringe((1, (2, 3), ((4,), 5))))
[1, 2, 3, 4, 5]
>>> list(fringe(7))
[7]
>>> same_fringe(((1, 2), 3), (1, (2, 3)))
True
>>> same_fringe((1, (2, 3)), (1, 2))
False
>>> same_fringe(((), 1), (1, ()))
True

発展

  • 先頭の葉で不一致になる大きな木の対を作り、same_fringe() が最初の不一致で走査を打ち切ることを確認してください（取り出された葉の枚数を数えるジェネレータを走査に挟むと観察できます）。フリンジをリストに全展開してから比較する実装と、計算量とメモリの両面で何が違うかを述べてください。
  • 再帰版の fringe() は、深さ \(d\) の木で1枚の葉を取り出すたびに最悪 \(O(d)\) 個のジェネレータフレームを経由し、Python の最大再帰深度の制約も受けます。スタックを明示的に管理する反復版を書き、最大再帰深度を超える深さの木で動作を比較してください。

参考