Как найти дублированные подмножества из нескольких наборов?

Question

У меня есть несколько наборов, таких как:

A={0, 2, 3, 4}

B={1, 2, 4}

C={0, 1, 5}

Затем я нашел подмножества каждого набора:

SubsetA=[{0}, {2}, {3}, {4}, {0, 2}, {0, 3}, {0, 4}, {2, 3}, {2, 4}, {3, 4}, {0, 2, 3}, {0, 2, 4}
         {0, 3, 4}, {2, 3, 4}, {0, 2, 3, 4}]

SubsetB=[{1}, {2}, {4}, {1, 2}, {1, 4}, {2, 4}, {1, 2, 4}]

SubsetC=[{0}, {1}, {5}, {0, 1}, {0, 5} {1, 5}, {0, 1, 5}]

Я хотел бы найти дублированные подмножества удалить их из окончательного вывода. Например, результат вышеприведенного примера равен 24 , поскольку после удаления дубликатов осталось 24 подмножества:

{0}, {2}, {3}, {4}, {0, 2}, {0, 3}, {0, 4}, {2, 3}, {2, 4}, {3, 4}, {0, 2, 3}, {0, 2, 4}
{0, 3, 4}, {2, 3, 4}, {0, 2, 3, 4}, {1}, {1, 2}, {1, 4}, {1, 2, 4}, {5}, {0, 1},
{0, 5}, {1, 5}, {0, 1, 5}

Я могу найти все подмножества с помощью python скрипт (он находит подмножества только одного набора); однако я не уверен, как найти дублированные подмножества нескольких наборов и удалить их.

Мне не нужно генерировать эти подмножества. Вместо этого мне нужно найти только число 24. Как в приведенном выше примере.

Примечание: у меня есть максимум 4 комплекта с размерами в диапазоне от 15 до 35 следующим образом:

A={32, 33, 8, 9, 10, 11, 12, 13, 14, 15, 27, 28, 29, 30, 31}

B={0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 34, 35, 36, 37, 38, 39, 40, 41}

C={0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 35, 43}

D={34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48}

Is есть предложения?

мой код подмножества:

def subsetsUtil(A, subset, index): 
    print(*subset) 
    for i in range(index, len(A)):  

        # include the A[i] in subset.  
        subset.append(A[i]) 

        # move onto the next element.  
        subsetsUtil(A,subset, i + 1)  

        # exclude the A[i] from subset and  
        # triggers backtracking. 
        subset.pop(-1)  
    return

    # below function returns the subsets of vector A.  
def subsets(A): 
    global res 
    subset = [] 

    # keeps track of current element in vector A  
    index = 0
    subsetsUtil(A, subset, index)  

    # Driver Code 

    # find the subsets of below vector.  
    array = [0, 2, 3, 4]

    # res will store all subsets.  
    # O(2 ^ (number of elements inside array))  
    # because at every step we have two choices  
    # either include or ignore.  
    subsets(array)  

Answer 1

Вы пишете, что некоторые из ваших наборов имеют 35 элементов, что означает, что они имеют ~ 34 миллиард подмножеств. Генерация, объединение и подсчет всех этих подмножеств на самом деле не вариант. Если вам нужно просто общее количество подмножеств, а не сами подмножества, вы можете рассчитать количество подмножеств каждого отдельного набора как 2 ⁿ -1 и объединить их для всех комбинаций 1, 2, 3. , ... sets.

>>> sets = [{0, 2, 3, 4}, {1, 2, 4}, {0, 1, 5}, {1, 2, 3, 4, 5}]
>>> num_subsets = lambda s: 2**len(s) - 1
>>> [num_subsets(s) for s in sets]
[15, 7, 7, 31]
# "naive" solution for reference
>>> len(set(frozenset(c) for s in sets for i in range(1, len(s)+1)
...                      for c in combinations(s, i)))
...
42
# combining subset counts of combinations of sets
>>> sum((-1)**k * sum(num_subsets(reduce(set.intersection, s))
...                   for s in combinations(sets, k+1)) 
...     for k in range(len(sets)))
...
42

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

Конечно, это довольно бесполезно вычисляет все комбинации из N множеств, даже если между ними не может быть никакого пересечения (не необходимо проверить пересечение A & B & X, если A & B уже является пустым набором), так что вы можете расширить его до go "глубже", если текущий выбор наборов все еще имеет общие элементы, но это оставлено в качестве упражнения для заинтересованный читатель. (Но если у вас в любом случае «максимум 4 комплекта», то это действительно не обязательно.)

---

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

>>> gen_sets = lambda n, m: [{random.randint(0,2*n) for _ in range(n)}
...                          for _ in range(m)]
...    
>>> sets = gen_sets(15, 10) # few sets, many elements
>>> %timeit naive()
10 loops, best of 3: 168 ms per loop
>>> %timeit this()
100 loops, best of 3: 4.73 ms per loop

>>> sets = gen_sets(10, 15) # many sets, few elements
>>> %timeit naive()
100 loops, best of 3: 11.6 ms per loop
>>> %timeit this()
10 loops, best of 3: 162 ms per loop

Если и количество элементов, и количество наборов велико (-i sh), вышеупомянутая оптимизация может помочь, но даже тогда это тривиально строить случаи, когда пересечения не могут быть удалены, например, если все наборы имеют общий элемент.

Answer 2

Просто используйте ... set, если хотите найти уникальные элементы!

tot = set((frozenset(i) for i in SubsetA +SubsetB+SubsetC))
print(len(tot))

дает 23

Мне пришлось использовать frozenset, потому что в качестве набора изменяемый тип, он не может быть хэшируемым и не может использоваться в наборе или в качестве ключа в диктовке. Если вам нужен список простых наборов, просто используйте другое понимание:

print([set(i) for i in tot])

дает:

[{0, 2, 3}, {1, 2}, {1, 5}, {1, 2, 4}, {5}, {0, 1, 5}, {3}, {0}, {0, 5}, 
 {2, 3, 4}, {3, 4}, {2, 3}, {0, 2}, {2}, {0, 1}, {0, 4}, {0, 2, 3, 4}, {4}, 
 {0, 3}, {2, 4}, {0, 3, 4}, {1, 4}, {1}]

Answer 3

Вот возможное решение:

from itertools import combinations

sets = [{0, 2, 3, 4}, {1, 2, 4}, {0, 1, 5}]
result = set(frozenset(c)
             for s in sets
             for i in range(len(s)+1)
             for c in combinations(s, i))

Мое решение включает также пустой набор.

Answer 4

Вот пример. Вам просто нужно объединить все подмножества, которые вы получаете, в один список, где подмножество представляет с помощью кортежа.

sets = [(6,5), (4,5), (5,6), (6,5)]

sets_sorted = list(map(lambda x: tuple(sorted(x)),sets))
unique_sets = list(set(sets_sorted))
# Unique sets: [(4, 5), (5, 6)]

В основном вы сортируете tuple, если одинаковые числа появляются в другом порядке в подмножество, а затем вы преобразуете их обратно в tuple. Это необходимо для того, чтобы set удалил дубликаты, потому что tuple - это тип с хэшированием. Затем кортежи помещаются в set, который удаляет дубликаты, а затем преобразуются обратно в list. Затем вы можете получить к ним доступ или получить их счет по len(unique_sets).