Pythoni c и эффективный способ найти все разные пересечения между двумя разделами одного и того же набора

Question

Мне нужно найти все разные пересечения между двумя разделами одного и того же набора. Например, если у нас есть следующие два раздела одного и того же набора

x = [[1, 2], [3, 4, 5], [6, 7, 8, 9, 10]]
y = [[1, 3, 6, 7], [2, 4, 5, 8, 9, 10]]

, требуемый результат будет

[[1], [2], [3], [4, 5 ], [6, 7], [8, 9, 10]].

Подробно мы вычисляем декартово произведение между каждым подмножеством x и y, и для каждого из этих произведений мы классифицируем элементы в новых подмножествах соответственно, принадлежат ли они пересечению связанных с ними подмножеств или нет.

Каков оптимальный / более pythoni c способ сделать это? Заранее благодарим!

---

СРАВНЕНИЕ ПРОИЗВОДИТЕЛЬНОСТИ ТЕКУЩИХ ОТВЕТОВ:

import numpy as np

def partitioning(alist, indices):
    return [alist[i:j] for i, j in zip([0]+indices, indices+[None])]

total = 1000
sample1 = np.sort(np.random.choice(total, int(total/10), replace=False))
sample2 = np.sort(np.random.choice(total, int(total/2), replace=False))

a = partitioning(np.arange(total), list(sample1))
b = partitioning(np.arange(total), list(sample2))

def partition_decomposition_product_1(x, y):
    out = []
    for sublist1 in x:
        d = {}
        for val in sublist1:
            for i, sublist2 in enumerate(y):
                if val in sublist2:
                    d.setdefault(i, []).append(val)
        out.extend(d.values())
    return out

def partition_decomposition_product_2(x, y):
    all_s = []
    for sx in x:
        for sy in y:
            ss = list(filter(lambda x:x in sx, sy))
            if ss:
                all_s.append(ss)
    return all_s

def partition_decomposition_product_3(x, y):
    return [np.intersect1d(i,j) for i in x for j in y]

И измеряя время выполнения с помощью% timeit

%timeit partition_decomposition_product_1(a, b)
%timeit partition_decomposition_product_2(a, b)
%timeit partition_decomposition_product_3(a, b)

находим

2.16 s ± 246 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
620 ms ± 84.7 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
1.03 s ± 111 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

, поэтому второе решение является самым быстрым.

Answer 1

Я могу пропустить некоторые детали, но это кажется слишком простым:

[np.intersect1d(a,b) for a in x for b in y]

Вывод:

[array([1]),
 array([2]),
 array([3]),
 array([4, 5]),
 array([6, 7]),
 array([ 8,  9, 10])]

Вышеупомянутое включает дубликаты, например x=[[1,2,3],[1,4,5]] и y=[[1,6,7]] даст [[1],[1]].

---

Если вы хотите найти уникальные пересечения:

[list(i) for i in {tuple(np.intersect1d(a,b)) for a in x for b in y}]

Вывод:

[[8, 9, 10], [6, 7], [1], [4, 5], [2], [3]]

Answer 2

Я не уверен, правильно ли я вас понял, но этот скрипт дает результат, который вы указали в вашем вопросе:

x = [[1, 2], [3, 4, 5], [6, 7, 8, 9, 10]]
y = [[1, 3, 6, 7], [2, 4, 5, 8, 9, 10]]

out = []
for sublist1 in x:
    d = {}
    for val in sublist1:
        for i, sublist2 in enumerate(y):
            if val in sublist2:
                d.setdefault(i, []).append(val)
    out.extend(d.values())

print(out)

Печать:

[[1], [2], [3], [4, 5], [6, 7], [8, 9, 10]]

Answer 3

Тот факт, что два списка являются разделами одного и того же набора, не имеет отношения к выбору алгоритма. Это сводится к перебору двух списков списков и получению пересечения между каждой комбинацией (вы можете добавить это утверждение в начале функции, чтобы убедиться, что они являются разделами одного и того же набора, используя этот ответ , чтобы сгладить списки эффективно). Имея это в виду, эта функция выполняет задачу, используя этот ответ для вычисления пересечения списков:

def func2(x, y):
    # check that they partition the same set 
    checkx = sorted([item for sublist in x for item in sublist])
    checky = sorted([item for sublist in y for item in sublist])
    assert checkx == checky

    # get all intersections
    all_s = []
    for sx in x:
        for sy in y:
            ss = list(filter(lambda x:x in sx, sy))
            if ss:
                all_s.append(ss)
    return all_s

Затем, используя этот метод сравнения времени , мы можем увидеть что эта новая функция примерно в 100 раз быстрее вашей исходной реализации.