在python中找到树中所有可能的路径 [英] find all possible paths in a tree in python

问题描述

我正在尝试创建一个包含树中所有可能路径的列表.我给出了以下结构(来自 DB 的子集):

I am trying to create a list with all possible paths in a tree. I have following structure given (subset from DB):

text = """
1,Product1,INVOICE_FEE,
3,Product3,INVOICE_FEE,
7,Product7,DEFAULT,
2,Product2,DEFAULT,7
4,Product4,DEFAULT,7
5,Product5,DEFAULT,2
"""

其中的列是:ID、产品名称、发票类型、对父 ID 的引用.我想创建包含所有可能路径的列表，如示例中所示:

where the columns are: ID, product-name, invoice-type, reference-to-parent-ID. I would like to create list with all possible paths, like in the example:

[[Product1],[Product3],[Product7,Product2,Product5],[Product7,Product4]]

我执行以下操作:

lines = [ l.strip() for l in text.strip().splitlines() ]
hierarchy = [ tuple(l.split(',')) for l in lines ]

parents = defaultdict(list)
for p in hierarchy:
    parents[p[3]].append(p)

为了创建树，然后我想找到所有路径:

for creation the tree and then I would like to find all paths:

def pathsMet(parents, node=''):
    childNodes = parents.get(node)
    if not childNodes:
        return []
    paths = []
    for ID, productName, invoiceType, parentID in childNodes:
        paths.append([productName] + pathsMet(parents, ID))
    return paths

print(pathsMet(parents))

我得到的结果如下:

[['FeeCashFlow1'], ['FeeCashFlow3'], ['PrincipalCashFlow7', ['AmortisationCashFlow3', ['AmortisationCashFlow2']], ['AmortisationCashFlow4']]]

如何更正代码以获得以下输出:

How to correct the code to have following output:

[['FeeCashFlow1'], ['FeeCashFlow3'], ['PrincipalCashFlow7', 'AmortisationCashFlow3', 'AmortisationCashFlow2'], ['PrincipalCashFlow7','AmortisationCashFlow4']]

推荐答案

您的代码似乎是正确的，只是您将整个列表附加到 paths 变量，而不是列表元素.

Your code seems correct except that you are appending entire list to the paths variable, instead of list elements.

试试这个修改:

def pathsMet(parents, node=''):
    childNodes = parents.get(node)
    if not childNodes:
        return [[]]
    paths = []
    for ID, productName, invoiceType, parentID in childNodes:
        for p in pathsMet(parents, ID):
            paths.append([productName] + p)
    return paths

这篇关于在python中找到树中所有可能的路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！