Nous sommes fournis avec 5 ensembles différents:
def isnotarr(k,rs):
for j in k:
if j in rs:
return True
return False
def most_frequent(List):
return max(set(List), key = List.count)
##s1 = set(["a", "b", "c"])
##s2 = set(["c", "d"])
##s3 = set(["a", "g", "h"])
##s4 = set(["d", "e", "f"])
##s5 = set(["g", "k", "l"])
set_list = [set(i) for i in r]
return_set = []
while len(set_list) > 0:
elements = []
for s in set_list:
for el in s:
elements.append(el)
element = most_frequent(elements)
return_set.append(element)
new_set_list = []
for s in set_list:
if element not in s:
new_set_list.append(s)
set_list = new_set_list
print "================initial set found============\n"
print(return_set)
print "================initial set found============\n"
def isvalidcomb(cm):
for el in r:
if isnotarr(el,cm):
pass
else:
return False
return True
def bfopt(n):
combs = itertools.combinations(return_set,n)
for i in combs:
if isvalidcomb(i):
return i
return None
for i in range(len(return_set),0,-1):
print "===========computing sets for maxlen %d============\n"%(i)
tmp = bfopt(i)
if tmp is not None:
print tmp
5 Réponses :
Voici comment je l'ai fait.
def most_frequent(List):
return max(set(List), key = List.count)
s1 = set(["a", "b", "c"])
s2 = set(["c", "d"])
s3 = set(["a", "g", "h"])
s4 = set(["d", "e", "f"])
s5 = set(["g", "k", "l"])
set_list = [s1, s2, s3, s4, s5]
return_set = []
while len(set_list) > 0:
elements = []
for s in set_list:
for el in s:
elements.append(el)
element = most_frequent(elements)
return_set.append(element)
new_set_list = []
for s in set_list:
if element not in s:
new_set_list.append(s)
set_list = new_set_list
print(return_set)
Premier: chaque ensemble peut être représenté par une puissance de 2: Chaque lettre peut être considérée comme un élément de poids 1 qui a une certaine valeur.
La valeur d'une lettre peut être évaluée comme la somme des ensembles qu'elle représente.
par exemple: A représente Maintenant, vos objectifs sont de trouver la quantité d'itens avec un poids minimal de telle sorte que la somme de ses valeurs est (1 + 2 + 4 + 8 + 16) = 31. Ceci est fondamentalement le Problème de Knapsack , un problème de programmation dynamique bien connu. Chaque élément serait une lettre et votre sac à dos a la taille 5 (au plus). Vous devez avoir une valeur de 31 dans cette taille.
Quant à la valeur de chaque lettre, vous pouvez simplement préprocéder. Si = 2 ^ (I-1) .
Ceci est très similaire au code que j'ai implémenté ci-dessous. La seule différence est que, au lieu d'attribuer à chaque réglage une valeur basée sur une puissance de 2, j'ai simplement supprimé les ensembles de la considération une fois qu'un élément de cet ensemble a été ajouté à la liste. De cette façon, vous comptez simplement des occurrences de chaque élément dans les ensembles restants de chaque itération.
Je ne suis pas très dans Python, je n'ai donc pas examiné le code profondément, mais je voulais dire que ce problème est également un cas du problème du sac à dos.
Totalement! Votre réponse ajoute beaucoup de valeur, je voulais juste le connecter à ma réponse pour que quiconque soit lu.
La réponse de Connor fonctionne très bien, mais il ne semble pas trouver les solutions optimales pour une grande quantité d'ensembles (N> 10000).
Vous pouvez utiliser iTERTOOLS.COMBINATIONS CODE> pour choisir un nombre croissant d'éléments de tous les éléments distincts et vérifiez si le jeu d'éléments cueilli a au moins un élément de chaque ensemble dans la liste: [{'f', 'c', 'g'},
{'e', 'c', 'g'},
{'a', 'd', 'g'},
{'b', 'd', 'g'},
{'c', 'd', 'g'},
{'a', 'd', 'l'},
{'a', 'd', 'k'}]
Ceci est précisément la
Il y a une autre façon d'y aller, comme je viens d'apprendre. Essentiellement, chaque élément est une variable bool et chaque jeu est une collection de contraintes ou . Chaque ensemble doit retourner true avec le nombre minimum d'éléments définis sur true . Cela s'avère être très facile à résoudre par un solveur linéaire tel que Z3. Il suffit de définir la somme des sommes de true dans chaque ensemble comme variable à minimiser et de voile.
Que voulez-vous dire que chaque ensemble est représenté au moins une fois? Voulez-vous dire, de sorte qu'au moins un élément de chaque ensemble apparaisse?
Oui exactement, ce que ce que je veux dire
Ce semble être votre question de manière plus informatisée