在Python中查找列表中的共同元素

Question

在Python中如何找到列表中的共同元素？

假设我有一个这样的列表：

[[a,b],[a,c],[b,c],[c,d],[e,f],[f,g]]

我想要的输出是：

[a,b,c,d]

[e,f,g]

我该怎么做呢？

我尝试过这样的方式：

for i in range(0,len(fin3)):
    for j in range(i+1,len(fin3)):
        grop = []
        grop = list(set(fin3[i]) & set(fin3[j]))
        if len(grop)>0:
            grop2 = []
            grop2.append(link[i])
            grop2.append(link[j])
            grop3.append(grop2)

提前谢谢你...

Answer 1

另一种方法，效率大概也是差不多的 -- O(n^2)，这里的 n 是指项目的数量。虽然这方法不是特别优雅，但它是正确的。如果你给名为 return_sets 的参数传入 True，那么下面的函数会返回一组（可以哈希的）不可变集合；如果不传这个参数，默认会返回一个列表的列表（正如你问题中提到的那样，这是你真正想要的）：

def create_equivalence_classes(relation, return_sets=False):
    eq_class = {}
    for x, y in relation:
        # Use tuples of x, y in case either is a string of length > 1 (iterable),
        # and so that elements x, y can be noniterables such as ints.
        eq_class_x = eq_class.get(x, frozenset( (x,) ))
        eq_class_y = eq_class.get(y, frozenset( (y,) ))
        join = eq_class_x.union(eq_class_y)
        for u in eq_class_x:
            eq_class[u] = join
        for v in eq_class_y:
            eq_class[v] = join
    set_of_eq_classes = set(eq_class.values())
    if return_sets:
        return set_of_eq_classes
    else:
        return list(map(list, set_of_eq_classes))

使用方法：

>>> data = [['a','b'], ['a','c'], ['b','c'], ['c','d'], ['e','f'], ['f','g']]
>>> print(create_equivalence_classes(data))
[['d', 'c', 'b', 'a'], ['g', 'f', 'e']]
>>> print(create_equivalence_classes(data, return_sets=False))
{frozenset({'d', 'c', 'b', 'a'}), frozenset({'g', 'f', 'e'})}

>>> data1 = [['aa','bb'], ['bb','cc'], ['bb','dd'], ['fff','ggg'], ['ggg','hhh']]
>>> print(create_equivalence_classes(data1))
[['bb', 'aa', 'dd', 'cc'], ['hhh', 'fff', 'ggg']]

>>> data2 = [[0,1], [2,3], [0,2], [16, 17], [21, 21], [18, 16]]
>>> print(create_equivalence_classes(data2))
[[21], [0, 1, 2, 3], [16, 17, 18]]

Answer 2

正如上面评论中提到的，看起来你想要进行集合合并。

这里有一个我根据上面评论中链接的代码调整的解决方案。

def consolidate(seq):
    if len(seq) < 2:
        return seq
    result, tail = [seq[0]], consolidate(seq[1:])
    for item in tail:
        if result[0].intersection(item):
            result[0].update(item)
        else:
            result.append(item)
    return result

def main():
    sets = [set(pair) for pair in [['a','b'],['a','c'],['b','c'],['c','d'],['e','f'],['f','g']]]
    print("Input: {0}".format(sets))
    result = consolidate(sets)
    print("Result: {0}".format(result))

if __name__ == '__main__':
    main()

示例输出：

Input: [set(['a', 'b']), set(['a', 'c']), set(['c', 'b']), set(['c', 'd']), set(['e', 'f']), set(['g', 'f'])]
Result: [set(['a', 'c', 'b', 'd']), set(['e', 'g', 'f'])]

Answer 3

我觉得你想要的是这样的：

data = [[1, 2], [2, 3], [4, 5]]

output = []

for item1, item2 in data:
    for item_set in output:
        if item1 in item_set or item2 in item_set:
            item_set.update((item1, item2))
            break
    else:
        output.append(set((item1, item2)))

output = map(list, output)

这样会得到：

output == [[1, 2, 3], [4, 5]]

Answer 4

如果你想找到一些共同的元素，即使这些列表不相邻，并且结果的顺序不重要：

def condense_sets(sets):
    result = []
    for candidate in sets:
        for current in result:
            if candidate & current:   # found overlap
                current |= candidate  # combine (merge sets)

                # new items from candidate may create an overlap
                # between current set and the remaining result sets
                result = condense_sets(result) # merge such sets
                break
        else:  # no common elements found (or result is empty)
            result.append(candidate)
    return result

举个例子：

>>> data = [['a','b'], ['a','c'], ['b','c'], ['c','d'], ['e','f'], ['f','g']]
>>> map(list, condense_sets(map(set, data)))
[['a', 'c', 'b', 'd'], ['e', 'g', 'f']]

可以查看这个链接：在保持顺序的情况下，将列表中的列表替换为“压缩”的列表。