算法在Python中的实现

Question

我有某些算法需要实现。基本上规则是：

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)

只是无法正确执行。我缺少什么？多谢。

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

结果列表中的每个单词都位于其所有“定义”单词之后。