J'ai une liste d'ensembles:

graphs = [{1, 2, 3}, {4, 5}, {6}]

Je dois vérifier si input ensemble peut être créé en tant que somme d'ensembles à l'intérieur de graphs.
Par exemple:

input1 = {1, 2, 3, 6} # answer - True
input2 = {1, 2, 3, 4} # answer - False, because "4" is only a part of another set, only combinations of full sets are required 

En d'autres termes, il y a toutes les combinaisons d'ensembles à l'intérieur de graphs:

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

J'ai besoin de savoir si l'une de ces combinaisons est égale à input.

Comment dois-je parcourir correctement les éléments graphs pour obtenir une réponse? Si graphs est plus grand, il y aurait des problèmes pour trouver toutes les combinaisons.

1
Angelika 25 oct. 2020 à 14:05

2 réponses

Meilleure réponse

Je pense que vous regardez cela de la mauvaise façon. Je pense qu'il est préférable de supprimer tout ensemble contenant un élément que vous ne pouvez pas utiliser (c'est-à-dire supprimer l'ensemble {4,5} lorsque vous recherchez {1,2,3,4}. Ensuite, créez union de tous les autres ensembles et voyez si c'est égal à votre jeu d'entrée.

De cette façon, vous n'aurez pas besoin de trouver toutes les combinaisons, juste une étape d'élimination (au plus) O (n * len (ensembles)) au début.

graphs = [i for i in graphs if i.issubset(input1)  ]

Vérifier la réponse:

result = set().union(*graphs) == input1
3
Christian Sloper 25 oct. 2020 à 11:55

Vous pouvez trouver toutes les combinaisons avec itertools.combinations, puis comparer simplement les ensembles:

from itertools import combinations, chain

def check(graphs, inp):
    for i in range(1, len(graphs)+1):
        for p in combinations(graphs, i):
            if set(chain(*p)) == inp:
                return True
    return False

graphs = [{1, 2, 3}, {4, 5}, {6}]
input1 = {1, 2, 3, 6}
input2 = {1, 2, 3, 4}

print(check(graphs, input1))
print(check(graphs, input2))

Tirages:

True
False
1
Andrej Kesely 25 oct. 2020 à 11:11