删除多级重复路径

Question

我有一个形成树的产品列表(ID、产品名称、发票类型、对父ID的引用(：

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

以下代码创建路径：

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)
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

结果路径列表：

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

可能是某些路径将被重复的情况，例如，对于列表：

text = """
7,Product7,DEFAULT,
2,Product2,DEFAULT,7
4,Product4,DEFAULT,7
5,Product4,DEFAULT,7
"""

将是(可能是多级嵌套路径复制(：

[['Product7'], ['Product7', 'Product2'], ['Product7', 'Product4'], ['Product7', 'Product4']]

如何去除重复的路径，但路径内部仍有正确的顺序？

Answer 1

paths = [['Product7'], ['Product7', 'Product2'], ['Product7', 'Product4'], ['Product7', 'Product4']]
def remove_duplicates(paths):
new_paths = []
s = set()
for path in paths:
t = tuple(path)
if t not in s:
new_paths.append(path)
s.add(t)
return new_paths
print(remove_duplicates(paths))

打印：

[['Product7'], ['Product7', 'Product2'], ['Product7', 'Product4']]

将每个路径转换为元组，并检查它是否已经在一个集合中(您不能将列表添加到集合中，因此我们将列表转换为元组(。如果不是，我们将路径添加到新的路径列表和集合中，否则我们知道它是一个重复的路径。

您实际上不需要单独的函数来删除重复项。您可以有一组路径，最初为空，在添加新路径之前，请检查remove_duplicates正在执行的功能类型：

s = set()
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):
path = [productName] + p
t = tuple(path)
if t not in s:
paths.append(path)
s.add(t)
return paths