python - 将成对等效值列表转换为所有等效值列表的算法？

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]，我将从 [ [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])]