LA2 | Treino 4 | União

'''
Implemente uma função que dada uma lista de conjuntos de inteiros determine qual
o menor número desses conjuntos cuja união é idêntica à união de todos os 
conjuntos recebidos.
'''


# testa se o candidato c está completo
def complete(p,c,i,ind):
    return len(c) == i

# enumera as extensões válidas para o candidato parcial c
def extensions(p,c,ind):
    return [a for a in p if p.index(a)>ind and a not in c]

# testa se um candidato c é uma solução válida para p
def valid(p,c,m):
    new = set()
    for cand in c:
        new = new.union(cand)
    return len(new) == len(m)


def aux(p,c,i,m, ind):
    if complete(p,c,i,ind):
        return valid(p,c,m)
    
    for x in extensions(p,c,ind):
        c.append(x)
        if aux(p,c,i,m,p.index(x)):
            return True
        c.pop()
    return False


def uniao(sets):
    flag = True
    max_set = set()
    
    for sett in sets:
        if max_set.intersection(sett):
            flag = False
        max_set = max_set.union(sett)
        
    if flag:
        return len(sets)
    
    for i in range(0, len(sets)+1):
        if aux(sets, [], i, max_set, -1):
            return i
    return len(sets)

Testes

# 1
sets = [{1,2,3},{2,4},{3,4},{4,5}]
> Resultado = 2

# 2
sets = [{1},{2},{3,4},{5,6,7,8},{1,3,5,7},{2,4,6,8},{9}]
> Resultado = 3