组合列表中的集合

Question

您好，我正在尝试执行以下操作，但遇到了一些困难。假设我有一个集合列表：

A = [set([1,2]), set([3,4]), set([1,6]), set([1,5])]

我想创建一个如下所示的新列表：

B = [ set([1,2,5,6]), set([3,4]) ]

即创建一个集合列表，如果集合重叠则将它们连接起来。这可能很简单，但今天早上我不太明白。

Answer 1

这是一个函数，可以满足您的需求。可能不是最 pythonic 的，但可以完成工作，很可能可以改进很多。

from sets import Set

A = [set([1,2]), set([3,4]), set([2,3]) ]

merges = any( a&b for a in A for b in A if a!=b)
while(merges):
    B = [A[0]]
    for a in A[1:] :
        merged = False
        for i,b in enumerate(B):
            if  a&b :
                B[i]=b | a
                merged =True
                break

        if not merged:         
            B.append(a)
    A = B
    merges = any( a&b for a in A for b in A if a!=b)

print B

下面发生了什么，我们循环 A 中的所有集合（除了第一个，因为我们已经将其添加到 B。我们检查与 B 中所有集合的交集，如果交集结果不是假（又名空集）我们在集合上执行联合并开始下一次迭代，关于集合操作检查此页面： https://docs.python.org/2/library/sets.html & 是交集运算符 |是联合运算符

您可能可以使用 any() 等进行更多的 pythonic，但是 wuold 需要更多处理，所以我避免了

Answer 2

怎么样：

from collections import defaultdict

def sortOverlap(listOfTuples):

    # The locations of the values
    locations = defaultdict(lambda: [])

    # 'Sorted' list to return
    sortedList = []

    # For each tuple in the original list
    for i, a in enumerate(listOfTuples):

        for k, element in enumerate(a):

            locations[element].append(i)

    # Now construct the sorted list
    coveredElements = set()
    for element, tupleIndices in locations.iteritems():

        # If we've seen this element already then skip it
        if element in coveredElements:
            continue

        # Combine the lists
        temp = []
        for index in tupleIndices:

            temp += listOfTuples[index]

        # Add to the list of sorted tuples
        sortedList.append(list(set(temp)))

        # Record that we've covered this element
        for element in sortedList[-1]:
            coveredElements.add(element)

    return sortedList

# Run the example (with tuples)
print sortOverlap([(1,2), (3,4), (1,5), (1,6)])

# Run the example (with sets)
print sortOverlap([set([1,2]), set([3,4]), set([1,5]), set([1,6])])

Answer 3

您可以在 for 循环中使用 intersection() 和 union()：

A = [set([1,2]), set([3,4]), set([1,6]), set([1,5])]

intersecting = []

for someSet in A:
    for anotherSet in A:
        if someSet.intersection(anotherSet) and someSet != anotherSet:
            intersecting.append(someSet.union(anotherSet))
            A.pop(A.index(anotherSet))

A.pop(A.index(someSet))

finalSet = set([])
for someSet in intersecting:
    finalSet = finalSet.union(someSet)

A.append(finalSet)

print A

输出：[set([3, 4]), set([1, 2, 5, 6])]

Answer 4

一个更直接的解决方案，

def overlaps(sets):
    overlapping = []
    for a in sets:
        match = False
        for b in overlapping:
            if a.intersection(b):
                b.update(a)
                match = True
                break
        if not match:
            overlapping.append(a)
    return overlapping

例子

>>> overlaps([set([1,2]), set([1,3]), set([1,6]), set([3,5])])
[{1, 2, 3, 5, 6}]
>>> overlaps([set([1,2]), set([3,4]), set([1,6]), set([1,5])])
[{1, 2, 5, 6}, {3, 4}]

Answer 5

for set_ in A:
    new_set = set(set_)
    for other_set in A:
        if other_set == new_set:
            continue
        for item in other_set:
            if item in set_:
                new_set = new_set.union(other_set)
                break
    if new_set not in B:
        B.append(new_set)

Input/Output:

A = [set([1,2]), set([3,4]), set([2,3]) ]
B = [set([1, 2, 3]), set([2, 3, 4]), set([1, 2, 3, 4])]

A = [set([1,2]), set([3,4]), set([1,6]), set([1,5])]
B = [set([1, 2, 5, 6]), set([3, 4])]

A = [set([1,2]), set([1,3]), set([1,6]), set([3,5])]
B = [set([1, 2, 3, 6]), set([1, 2, 3, 5, 6]), set([1, 3, 5])]

Answer 6

此函数将完成工作，无需触摸输入：

from copy import deepcopy


def remove_overlapped(input_list):
    input = deepcopy(input_list)
    output = []
    index = 1

    while input:
        head = input[0]
        try:
            next_item = input[index]
        except IndexError:
            output.append(head)
            input.remove(head)
            index = 1
            continue
        if head & next_item:
            head.update(next_item)
            input.remove(next_item)
            index = 1
        else:
            index += 1
    return output

Answer 7

这也有效，而且很短：

import itertools

groups = [{'1', '2'}, {'3', '2'}, {'2', '4'}, {'5', '6'}, {'7', '8'}, {'7','9'}]

while True:
    for s1, s2 in itertools.combinations(groups, 2):
        if s1.intersection(s2):
            break
    else:
        break
    groups.remove(s1)
    groups.remove(s2)
    groups.append(s1.union(s2))

groups

这给出了以下输出：

[{'5', '6'}, {'1', '2', '3', '4'}, {'7', '8', '9'}]

while True 对我来说确实有点危险，有人有什么想法吗？

组合列表中的集合

combining sets within a list

python

set