python - 分组 str 的分组列表而不重复

Question

我有一个字符串分组列表，看起来像这样，这些组内的列表将始终包含 5 个元素:

text_list = [['aaa','bbb','ccc','ddd','eee'],
['fff','ggg','hhh','iii','jjj'],
['xxx','mmm','ccc','bbb','aaa'],
['fff','xxx','aaa','bbb','ddd'],
['aaa','bbb','ccc','ddd','eee'],
['fff','xxx','aaa','ddd','eee'],
['iii','xxx','ggg','jjj','aaa']]

目标很简单，将所有相似的列表按前 3 个元素分组，然后将其与其他组内的所有元素进行比较。

所以从上面的例子来看，输出可能是这样的(输出是列表的索引):

[[0,2,4],[3,5]]

注意如果有另一个包含相同元素但顺序不同的列表是如何被删除的。

我编写了以下代码来提取组，但它们会返回重复项，我不确定如何继续。我还认为这可能不是最有效的提取方法，因为实际列表可能包含数百万个组:

grouped_list = []
for i in range(0,len(text_list)):
    int_temp = []
    for m in range(0,len(text_list)):
        if i == m:
            continue
        bool_check = all( x in text_list[m] for x in text_list[i][0:3])
        
        if bool_check:
            if len(int_temp) == 0:
                int_temp.append(i)
                int_temp.append(m)
                continue
            int_temp.append(m)
           
    
    grouped_list.append(int_temp)
    
## remove index with no groups
grouped_list = [x for x in grouped_list if x != []]

有没有更好的方法来解决这个问题？之后如何删除重复组？谢谢。

编辑:

为了更清楚，我想检索彼此相似但仅使用其他列表的前 3 个元素的列表。例如，使用列表 A 中的前 3 个元素，检查列表 B、C、D... 是否包含列表 A 中的所有 3 个元素。对整个列表重复此操作，然后删除包含重复元素的任何列表。

Answer 1

您可以构建一组卡住集来跟踪组的索引，前 3 项是其余成员的子集:

groups = set()
sets = list(map(set, text_list))
for i, lst in enumerate(text_list):
    groups.add(frozenset((i, *(j for j, s in enumerate(sets) if set(lst[:3]) <= s))))
print([sorted(group) for group in groups if len(group) > 1])

如果输入列表很长，创建一组所有子列表的前 3 项的 frozensets 并使用该集合从每个子列表中过滤 3 项的所有组合会更快，这样尽管生成组合的开销很大，但时间复杂度基本上与输入列表成线性关系而不是二次方:

from itertools import combinations

sets = {frozenset(lst[:3]) for lst in text_list}
groups = {}
for i, lst in enumerate(text_list):
    for c in map(frozenset, combinations(lst, 3)):
        if c in sets:
            groups.setdefault(c, []).append(i)
print([sorted(group) for group in groups.values() if len(group) > 1])