jsonデータの子idに対する親id、祖先idのリスト化

jsonファイルで

qiita.rb

[{"child_id":"AAA","parent_id":"AA"},{"child_id":"AA","parent_id":"A"},
{"child_id":"A","parent_id":"Alphabet"}]

のように子idと親idが連鎖しているとき、子とその祖先をまとめたリスト
["AAA","AA","A","Alphabet"]
を出力したい。

1000個のデータがそれぞれ親子関係を持つよう辞書に辞書型データのリストを作成。

qiita.rb

child_id_list = [i for i in range(1000)]
#子を10で割った商が親となる
parent_id_list = [item//10 for item in id_list]
dic= dict(zip(child_id_list,parent_id_list))
#dic_listの形式のjsonファイルを想定。
#読み込み後は子idと親idのリストから生成したdicを使う。
dic_list = [{k:v} for k,v in dic.items()]

child_id_listの要素ごとに、子idの親id、さらにその親idと遡っていき、子idとその祖先idをリスト化する再帰関数を作成。

qiita.rb

#child_id:child_id_listの各要素
#memo:メモ用の空の配列
def saiki(dic,child_id,memo):
    if len(memo) == 0:
        memo.append(id)
    memo.append(dic.get(id))
    if memo[-1] == 0:
        return memo
    id = memo[-1]
    return saiki(dic,id,memo) 

回してみる。

qiita.rb

import json

def saiki(dic,id,memo):
    if len(memo) == 0:
        memo.append(id)
    memo.append(dic.get(id))
    if memo[-1] == 0:
        return memo
    id = memo[-1]
    return saiki(dic,id,memo) 

child_id_list = [i for i in range(1000)]
parent_id_list = [item//10 for item in child_id_list]
dic= dict(zip(child_id_list,parent_id_list))

big_memo = []

for n in child_id_list:
    memo = []
    memo_a = saiki(dic,n,memo)
    big_memo.append(memo_a)
print(big_memo)

結果

[[0, 0], [1, 0], [2, 0], [3, 0], [4, 0], [5, 0], [6, 0], [7, 0], [8, 0], [9, 0], 
[10, 1, 0], [11, 1, 0], [12, 1, 0], [13, 1, 0], [14, 1, 0], 
[15, 1, 0], [16, 1, 0], [17, 1, 0], [18, 1, 0], [19, 1, 0], [20, 2, 0]…

以上のようにchild_id_listの子idを回して
[子id,親id,祖父id,…,祖先id]
のリストが得られた。

ここから[{子id:[親id,…祖先id]}]の辞書リストを作成すれば、子idが複数並ぶリストから特定の親idを祖先に持つものをフィルタリングしたりできる。