2011-11-13 231 views
1

我有一定的算法需要實現。基本上這些規則是:Python中的算法實現

  1. 一行上的第一個以空格分隔的標記將被定義的單詞。
  2. 後面的令牌將被定義。如果定義是「。」,則該單詞是原語,即沒有定義的單詞。
  3. 輸出是一個逗號分隔的單行文本,其中只包含一次字典中的每個單詞。每個單詞只能在其定義中的所有單詞後面打印。請注意,對於某些輸入集,可能有多個有效輸出。

例如輸入:

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) 

只是無法得到它的權利。我錯過了什麼?非常感謝。

回答

0
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'] 
>>> 

在結果列表中的每一個字談到畢竟它的 「定義」 的話。

+0

非常感謝。我不擅長圖表,以前從未考慮過使用圖表。 – user1044566

+0

如果此答案符合您的需求,請點擊其分數旁邊的複選標記。 – wberry