Удаление многоуровневых дублированных путей

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