Алгоритм для преобразования списка парных эквивалентных значений в списки всех эквивалентных значений?

Question

Я работаю над программой, которая должна иметь возможность удалять повторяющиеся значения из списка списков. Однако я могу определить повторяющиеся значения только путем парного сравнения. Когда я закончу со сравнениями, у меня есть список эквивалентных пар. Но мне нужен список всех эквивалентных значений для дальнейшей обработки, чтобы определить, какое из дублированных значений будет сохранено.

Я собрал вместе некоторый код, который, казалось, работал для нескольких элементов, но он не работает под нагрузкой, когда я пытаюсь использовать его для списков с несколькими тысячами записей. Код, который я использую:

    seen = []
    holding = []

    for dup_pair in all_dup_pairs:
        if dup_pair[0] not in seen and dup_pair[1] not in seen and dup_pair[0] not in holding:
            holding.append(dup_pair[0])
            holding.sort()
            seen.append(dup_pair[0])
            seen.append(dup_pair[1])
            seen.sort()
        if dup_pair[1] not in seen:
            seen.append(dup_pair[1])
            seen.sort()

    for item in holding:
        final_duplicates.append([item])

    for dup_pair in all_dup_pairs:
        for i in range(len(final_duplicates)):
            if dup_pair[0] in final_duplicates[i] and dup_pair[1] not in final_duplicates[i]:
                final_duplicates[i].append(dup_pair[1])

(да, я знаю, что это неэффективно и безобразно)

Так, например, если бы исходными элементами были [a, c, a, a, b, b, d, e, b, c], я бы начал с dup_pairs как [[0,2], [0 , 3], [1,9], [2,3], [4,5], [4,8], [5,8]] и я хотел бы в конечном итоге получить final_duplicates [[0,2, 3], [1,9] [4,5,8]]. Как я уже сказал, код работает на небольших примерах, подобных этому, но он не работает на гораздо больших версиях списка, которые мне нужны для производства, и вместо того, чтобы просто пытаться исправить код, я хотел бы попытаться сделать это «правильно». «чтобы я мог снова работать с ним через 18 месяцев, когда проблема снова возникнет. Спасибо всем, у кого есть предложения по правильному алгоритму.

Answer 1

вы можете сделать:

import re
x = ["a","c","a","a","b","b","d","e","b","c"]
s = ''.join(x)
[(v, [m.start() for m in re.finditer(v, s)]) for v in set(x)]

и результат:

[('c', [1, 9]), ('d', [6]), ('e', [7]), ('b', [4, 5, 8]), ('a', [0, 2, 3])]

Answer 2

Проверьте следующее:

def gum(l):
    g = {}
    for i, k in enumerate(l):
        g.setdefault(k, []).append(i)
    return g

x = 'acaabbdebc'
print(gum(x))

Вывод:

{'b': [4, 5, 8], 'a': [0, 2, 3], 'e': [7], 'd': [6], 'c': [1, 9]}