在一组集合中找到交集集合

Question

在一组集合中找到交集集合

3

以下问题涉及Python 3.6。假设我有一些集合的列表，例如：

L1 = [{2,7},{2,7,8},{2,3,6,7},{1,2,4,5,7}]      
L2 = [{3,6},{1,3,4,6,7},{2,3,5,6,8}]      
L3 = [{2,5,7,8},{1,2,3,5,7,8}, {2,4,5,6,7,8}]

我需要找到L1、L2和L3中每个元素之间的交集。例如：

    {2,7}.intersection({3,6}).intersection({2,5,7,8})= empty  
    {2,7}.intersection({3,6}).intersection({1,2,3,5,7,8})= empty  
    {2,7}.intersection({3,6}).intersection({2,4,5,6,7,8})= empty  
    {2,7}.intersection({1,3,4,6,7}).intersection({2,5,7,8})= {7}  
    {2,7}.intersection({1,3,4,6,7}).intersection({1,2,3,5,7,8})= {7}  
    {2,7}.intersection({1,3,4,6,7}).intersection({2,4,5,6,7,8})= {7}

如果我们一直按照这样的方式进行，最终得到以下集合：

{{空},{2},{3},{6},{7},{2,3},{2,5},{2,6},{2,8},{3,7},{4,7},{6,7}}

假设：
- 我有许多列表 L1、L2、L3、...Ln。而我不知道我有多少个列表。
- 每个列表 L1、L2、L3..Ln 都很大，所以我不能将它们全部加载到内存中。

我的问题是：是否有任何方法可以顺序地计算该集合，例如在 L1 和 L2 之间进行计算，然后使用结果与 L3 进行计算，依此类推...

- cdt

3个回答

1

你可以使用 functools.reduce(set.intersection, sets) 处理可变输入。而使用 itertools.product(nested_list_of_sets) 从多个序列中生成每个序列的一个元素的组合。

通过使用生成器函数 (yield) 和像 itertools.product 这样的惰性迭代器，您可以将内存使用量降低几个数量级。

import itertools
import functools

nested_list_of_sets = [
    [{2,7}, {2,7,8}, {2,3,6,7}, {1,2,4,5,7}], 
    [{3,6}, {1,3,4,6,7}, {2,3,5,6,8}],
    [{2,5,7,8}, {1,2,3,5,7,8}, {2,4,5,6,7,8}],
]

def find_intersections(sets):
    """Take a nested sequence of sets and generate intersections"""
    for combo in itertools.product(*sets):
        yield (combo, functools.reduce(set.intersection, combo))

for input_sets, output_set in find_intersections(nested_list_of_sets):
    print('{:<55}  ->   {}'.format(repr(input_sets), output_set))

输出是。

({2, 7}, {3, 6}, {8, 2, 5, 7})                           ->   set()
({2, 7}, {3, 6}, {1, 2, 3, 5, 7, 8})                     ->   set()
({2, 7}, {3, 6}, {2, 4, 5, 6, 7, 8})                     ->   set()
({2, 7}, {1, 3, 4, 6, 7}, {8, 2, 5, 7})                  ->   {7}
({2, 7}, {1, 3, 4, 6, 7}, {1, 2, 3, 5, 7, 8})            ->   {7}
({2, 7}, {1, 3, 4, 6, 7}, {2, 4, 5, 6, 7, 8})            ->   {7}
({2, 7}, {2, 3, 5, 6, 8}, {8, 2, 5, 7})                  ->   {2}
({2, 7}, {2, 3, 5, 6, 8}, {1, 2, 3, 5, 7, 8})            ->   {2}
# ... etc

在repl.it上的在线演示

- Håken Lid

1

考虑到他无法将所有列表保存在内存中，他还需要一种可迭代的惰性加载类型。特别是对于所有后续的列表，它需要被重置。这也意味着需要对数据进行序列化，因此很可能除了第一个列表外，没有必要将集合转换为实际的哈希集。 - Yann Vernier

这个问题有点难以解释。只有当所有的L1、L2、L3等都可用时，示例代码才有意义，以创建笛卡尔积。整个产品不在内存中，但输入必须可用以创建产品。 - Håken Lid

1

根据这个问题的最佳答案，itertools.product必须将其参数转换为元组。因此，它无法接受太大而无法放入内存的惰性序列。我认为可能可以实现一个笛卡尔积生成器，可以使用输入流工作。但我相信你需要一些方法来倒回序列。 - Håken Lid

谢谢您的帮助。实际上，我需要读取一个文件，其中一行表示一组集合。例如，行1：2,7|2,7,8|2,3,6,7|1,2,4,5,7 行2：3,6|1,3,4,6,7|2,3,5,6,8 行3：2,5,7,8|1,2,3,5,7,8|2,4,5,6,7,8我只能逐行读取文件。因此，我将读取每一行，通过“|”进行分割，并将每一行转换为一组集合。由于文件很大且每行很长，我无法将整个文件读入列表中。因此，对嵌套集合列表的定义对我来说似乎是不可能的。 - cdt

我认为修改我的答案以获得您想要的结果是可能的。您可以将若干行代码传递给find_intersections函数，创建一个输出列表，该列表可以随一些来自输入源的更多行代码一起传递回find_intersections函数。如果您对空集不感兴趣，您可能需要在每次迭代中修剪空集。 - Håken Lid

谢谢你的帮助。我也会尝试你的方法。 - cdt

0

这可能是你正在寻找的内容：

res = {frozenset(frozenset(x) for x in (i, j, k)): i & j & k \
       for i in L1 for j in L2 for k in L3}

解释

需要使用frozenset，因为set不可哈希。字典键必须是可哈希的。
循环遍历L1、L2、L3中每个长度为3的组合。
通过&操作计算交集，相当于set.intersection。

- jpp

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Norrius · Accepted Answer

你可以先计算L1和L2之间所有可能的交点，然后计算该集合与L3之间的交点，以此类推。

list_generator = iter([  # some generator that produces your lists 
    [{2,7}, {2,7,8}, {2,3,6,7}, {1,2,4,5,7}],      
    [{3,6}, {1,3,4,6,7}, {2,3,5,6,8}],      
    [{2,5,7,8}, {1,2,3,5,7,8}, {2,4,5,6,7,8}], 
])
# for example, you can read from a file:
# (adapt the format to your needs)
def list_generator_from_file(filename):
    with open(filename) as f:
        for line in f:
            yield list(map(lambda x: set(x.split(',')), line.strip().split('|')))
# list_generator would be then list_generator_from_file('myfile.dat')

intersections = next(list_generator)  # get first list
new_intersections = set()

for list_ in list_generator:
    for old in intersections:
        for new in list_:
            new_intersections.add(frozenset(old.intersection(new)))
    # at this point we don't need the current list any more
    intersections, new_intersections = new_intersections, set()

print(intersections)

输出结果看起来像这样：{frozenset({7}), frozenset({3, 7}), frozenset({3}), frozenset({6}), frozenset({2, 6}), frozenset({6, 7}), frozenset(), frozenset({8, 2}), frozenset({2, 3}), frozenset({1, 7}), frozenset({4, 7}), frozenset({2, 5}), frozenset({2})}，除了你错过的{1,7}集合之外，与你的匹配。