Pythonで家系の相続順序を求めるプログラムの実装方法

ある家族には、父親、その子どもたち、そして祖母といったように、異なる世代のメンバーが属しています。現実の家庭と同じように、この家族にも出生と死亡が絶えず起こります。

家族の中で最も年長のメンバーが「家長」とみなされます。家長が亡くなると、その直系の後継者、つまり子どもが新たな家長となります。

ここでは3つの関数を実装します。

• 1つ目はbirth()：家族に子どもが生まれたときに呼び出され、親の名前と子どもの名前を受け取って記録に追加します。
• 2つ目はdeath()：家族に死亡者が発生したときに呼び出され、故人の名前を受け取って記録から除外します。
• 3つ目はinheritance()：呼び出されるたびに、現在の相続順序を出力します。

一連の入力に対して相続順序を求めるのが目的です。たとえば、入力の順序が「birth、birth、birth、birth、birth、death、inheritance、death、inheritance」だった場合、出力は次のようになります。

['Zach', 'Jesse', 'Ursula', 'Ryan', 'Thea']
['Jesse', 'Ursula', 'Ryan', 'Thea']

具体例で流れを確認する

最初の家長はPaulです。

PaulにはZachとJesseという2人の子どもが生まれます。

次にJesseに3人の子ども、Ursula、Ryan、Theaが生まれます。Ursulaが一番上で、Theaが一番下です。

ここでPaulが死亡すると、相続順序は ['Zach', 'Jesse', 'Ursula', 'Ryan', 'Thea'] になります。

さらにZachが死亡すると、相続順序は ['Jesse', 'Ursula', 'Ryan', 'Thea'] へと更新されます。

解決のための手順

• family := 値としてリストを持つ新しい辞書（マップ）
• head := 現在の家長の名前
• dead := 死亡者を記録するセット
• 関数 birth(p_name, c_name) を定義
  • c_name を family[p_name] の末尾に追加する
• 関数 death(name) を定義
  • name をセット dead に追加する
• 関数 inheritance() を定義
  • ans := 新しいリスト
  • depth_search(head) を実行する
  • ans を返す
• 関数 depth_search(current) を定義
  • current が dead に含まれていない場合
    • current を ans の末尾に追加する
  • family[current] 内の各 child について
    • depth_search(child) を再帰的に呼び出す

ポイントは、死亡した人物を記録から物理的に削除するのではなく「deadセット」で管理することです。こうすることで、親子関係（ツリー構造）を壊さずに済み、相続順序が必要になった時点で深さ優先探索（DFS）によって生存者だけを順番に抽出できます。

実装例

以下のコードで実際の動作を確認してみましょう。

from collections import defaultdict
class Solution:

   def __init__(self, head_name):
      self.family = defaultdict(list)
      self.head = head_name
      self.dead = set()

   def birth(self, p_name, c_name):
      self.family[p_name].append(c_name)

   def death(self, name):
      self.dead.add(name)

   def inheritance(self):
      self.ans = []
      self.depth_search(self.head)
      return self.ans

   def depth_search(self, current):
      if current not in self.dead:
         self.ans.append(current)
      for child in self.family[current]:
         self.depth_search(child)

ob = Solution('Paul')
ob.birth('Paul', 'Zach')
ob.birth('Paul', 'Jesse')
ob.birth('Jesse', 'Ursula')
ob.birth('Jesse', 'Ryan')
ob.birth('Jesse', 'Thea')
ob.death('Paul')
print(ob.inheritance())
ob.death('Zach')
print(ob.inheritance())

入力

ob = Solution('Paul')
ob.birth('Paul', 'Zach')
ob.birth('Paul', 'Jesse')
ob.birth('Jesse', 'Ursula')
ob.birth('Jesse', 'Ryan')
ob.birth('Jesse', 'Thea')
ob.death('Paul')
print(ob.inheritance())
ob.death('Zach')
print(ob.inheritance())

出力

['Zach', 'Jesse', 'Ursula', 'Ryan', 'Thea']
['Jesse', 'Ursula', 'Ryan', 'Thea']