Как я могу получить два подмножества (SA, SB), учитывая два набора (A, B) и список L пар (a, b) st декартового произведения SA и SB в L?

Question

У меня есть два списка A и B, которые представляют два набора:

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

B = [a,b,c,d,e,f]

И список L, содержащий несколько пар (a, b) с принадлежностью A и b, принадлежащей B. Обратите внимание, что L не содержит всех возможных комбинаций.

L = [(1,a),(1,f),(2,d),(3,a),(3,f),(4,b),(5,f)]

Мне нужно найти SA и SB такие, что SA x SB (декартово произведение) находится в L, максимизируя | SA | * | SB | В примере

SA = [1,3] SB = [a,f]

Answer 1

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

from collections import defaultdict
from itertools   import combinations

def findProdSets(A,B,L):
    d = defaultdict(set)
    for a,b in L: d[a].add(b)
    for size in range(1,len(A)+1):
        for subsetA in combinations(A,size):
            subsetB = set.intersection(*(d[a] for a in subsetA))
            if len(subsetB)>0:
                yield subsetA,tuple(subsetB)

A = [1,2,3,4,5]
B = ["a","b","c","d","e","f"]
L = [(1,"a"),(1,"f"),(2,"d"),(3,"a"),(3,"f"),(4,"b"),(5,"f")]

subSetA,subSetB = max(findProdSets(A,B,L),key=lambda c:len(c[0])*len(c[1]))
print(subSetA,subSetB)               

(1, 3) ('a', 'f')

Чтобы оптимизировать это, вы можете изменить функцию findProdSets так, чтобы она возвращала пару наборов с наибольшим товар. Это позволило бы ему выйти рано, начиная с самого большого размера и останавливаясь, тогда size x len(A) меньше или равно наибольшему найденному продукту

Answer 2

я думаю, что это будет стоить O (n!)

from collections import defaultdict as dd
import itertools as it

a = [1,2,3,4,5,6,7,8]
b = ["a", "b", "c", "d"]

p = [i for i in it.product(a,b)]
p.remove(p[5])
p.remove(p[2])
p.remove(p[8])
#till here we create a list of tuples

dict_key_x = dd(set) #dict with x values as key and all y values in set as value
for tup in p:
    dict_key_x[tup[0]].add(tup[1])

max_len = 0
max_value = [-1,-1]

comb_x = [] #a list with all combination of all length from x values
for i in range(1,len(dict_key_x)+1):
    for j in it.combinations(dict_key_x.keys(),i):
        comb_x.append(j)

for comb in comb_x: #for every combination check the Intersection of the y values of all x
    mutual = dict_key_x[comb[0]]
    for x_value in comb:
        mutual = mutual & dict_key_x[x_value]
    if len(comb)*len(mutual)>max_len:
         max_len = len(comb)+len(mutual)
         max_value[0]=comb
         max_value[1] = mutual
print(max_value)
print(max_len)
print(p)