Pythonでのアルゴリズムの実装

Question

実装するアルゴリズムが必要です。基本的には、規則は以下の通りです。

1. 行の最初の空白で区切られたトークンは、定義されている単語になります。
2. 後のトークンが定義になります。定義が「。」の場合、その単語はプリミティブ、つまり定義のない単語です。
3. 出力は、カンマで区切られた1行のテキストで、辞書内の各単語が正確に1回だけ含まれます。各単語は、定義内のすべての単語の後にのみ印刷されます。特定の入力セットに対して、複数の有効な出力が存在する可能性があることに注意してください。たとえば、

入力：

Civic  Honda Car 
Honda  Manufacturer 
VW   Manufacturer 
Manufacturer . 
Car   . 
Beetle  VW Car 

いくつかの可能な出力：

Car, Manufactor, Honda, VW, Beetle, Civic 
Manufacturer, VW, Car, Beetle, Honda, Civic 
Manufacturer, Honda, VW, Car, Beetle, Civic 

私の実装：

def defIt(pre, cur): 
    # If previous and current strings are the same, no action take 
    if pre == cur: 
     return pre 

    # Split two strings to list 
    l_pre = pre.split() 
    l_cur = cur.split() 

    # If previous string length is shorter than the current string  length, then swap two lists 
    if len(l_pre) < len(l_cur): 
     l_pre, l_cur = l_cur, l_pre 

    found = False 


    for j, w_cur in enumerate(l_cur): 
     for i, w_pre in enumerate(l_pre): 
      if w_pre == w_cur: 
       found = True 
       return ' '.join(l_cur[j:] + l_cur[:j] + l_pre[:i] + l_pre[(i + 1):]) 


    if not found: 
     return ' '.join(l_cur[1:] + [l_cur[0]] + l_pre) 

だけは右のそれを得ることができません。何が欠けていますか？どうもありがとう。

Answer 1

def read_graph(lines): 
    g = {} 
    for line in lines: 
     words = line.split() 
     if words[1] == '.': 
      words = words[:1] 
     g[words[0]] = words[1:] 
    return g 

def dump_graph(g): 
    out = [] 
    def dump(key): 
     for k in g[key]: 
      dump(k) 
     if key not in out: 
      out.append(key) 
    for k in g: 
     dump(k) 
    return out 

使用法：

>>> data = """Civic  Honda Car 
... Honda  Manufacturer 
... VW   Manufacturer 
... Manufacturer . 
... Car   . 
... Beetle  VW Car 
... """ 
>>> g = read_graph(data.splitlines()) 
>>> g 
{'VW': ['Manufacturer'], 'Civic': ['Honda', 'Car'], 'Car': [], 
'Honda': ['Manufacturer'], 'Beetle': ['VW', 'Car'], 'Manufacturer': []} 
>>> dump_graph(g) 
['Manufacturer', 'VW', 'Honda', 'Car', 'Civic', 'Beetle'] 
>>> 

結果のリスト内のすべての単語は、そのすべての "定義" の言葉の後に来ます。