Python: 父子层次结构的组合

Question

针对一个包含父子关系的表格（csv格式），我正在尝试使用表格中的所有数据获取可能的父子关系组合链。我碰到的问题是，如果存在多个次级父母（参见第3和第4行），第二个次级父母组合（第4行）不会被包括在迭代中。

数据示例：

child,parent

A,B
A,C
B,D
B,C
C,D

预期的链结果:

D|B|A
D|C|B|A
D|C|A

实际的链结果：

D|B|A
D|C|A

代码

find= 'A' #The child for which the code should find all possible parent relationships
sequence = ''
with open('testing.csv','r') as f:     #testing.csv = child,parent table (above example)
    for row in f:
        if row.strip().startswith(find):
            parent = row.strip().split(',')[1]
            sequence = parent + '|' + find
            f1 = open('testing.csv','r')
            for row in f1:
                if row.strip().startswith(parent):
                    parent2 = row.strip().split(',')[1]
                    sequence = parent2 + '|' + sequence
                    parent = parent2
        else:
            continue
        print sequence

- Sarah Bergquist

---

我不理解这句话的意思： "我遇到了一个问题，即如果存在多个子父级（请参见第3和第4行），则第二个子父级组合（第4行）将不包括在迭代中" - 然而你列出了D|C|B|A 作为预期结果。如果排除第四行 B|C 组合，我认为这个结果不会出现。 - Gerrat

当前代码没有考虑第四行。这正是问题所在。 - Sarah Bergquist

顺便说一下，Sarah，看了你的个人资料，你提出了很多问题，也得到了很多人的回答。如果有人给出了你认为可以接受的答案，你应该通过点击其答案旁边的复选标记来“接受”它。到目前为止，你还没有接受任何答案。 - Gerrat

Answer 1

您看过这篇精彩的文章吗？它是了解Python中模式的基本阅读材料。您的问题可以看作是一个图形问题——查找关系就是从子节点到父节点找到所有路径。

由于可能存在任意数量的嵌套（子->父1->父2……），因此您需要使用递归解决方案来查找所有路径。在您的代码中，您有两个for循环——最多只能得到3级路径，正如您发现的那样。

下面的代码是从上面的链接中改编的，以解决您的问题。函数find_all_paths需要一个图形作为输入。

让我们从您的文件中创建图表：

graph = {} # Graph is a dictionary to hold our child-parent relationships.
with open('testing.csv','r') as f:
    for row in f:
        child, parent = row.split(',')
        graph.setdefault(parent, []).append(child)

print graph

使用您的示例，结果应该输出：

{'C': ['A', 'B'], 'B': ['A'], 'D': ['B', 'C']}

以下代码直接来自文章：

def find_all_paths(graph, start, end, path=[]):
    path = path + [start]
    if start == end:
        return [path]

    if not graph.has_key(start):
        return []

    paths = []

    for node in graph[start]:
        if node not in path:
            newpaths = find_all_paths(graph, node, end, path)
            for newpath in newpaths:
                paths.append(newpath)
    return paths

for path in find_all_paths(graph, 'D', 'A'):
    print '|'.join(path)

输出：

D|B|A
D|C|A
D|C|B|A

- vikramls

---

感谢您的文章，vikramis。这段代码正是我所需要的。 - Sarah Bergquist

Answer 2

我不确定这是否是最有效的方法（但在每行上再次读取文件会更糟糕）。

find= 'A' #The child for which the code should find all possible parent relationships
sequences = set(find)

# we'll build up a chain for every relationship, then strip out un-needed ones later
with open('testing.csv','r') as f:     #testing.csv = child,parent table (above example)
    for row in f:
        child, parent = row.strip().split(',')
        sequences.add(parent + '|' + child)
        for c in sequences.copy():  
            if c[0] == child:
                sequences.add(parent + '|' + c)


# remove any that don't end with our child:
sequences = set(s for s in sequences if s.endswith(find))

# get all shorter chains when we have a longer one
extra = set()
for g1 in sequences:
    for g2 in sequences:
        if g2[2:] == g1:
            extra.add(g1)

# remove the shorter chains
sequences.difference_update(extra)

for chain in sequences:
    print(chain)

结果：

D|C|A
D|C|B|A
D|B|A

- Gerrat