Disons que j'ai 10 ensembles, et chaque ensemble a une quantité aléatoire d'entiers positifs.

Maintenant, je veux maximiser le nombre d'ensembles qui peuvent former une intersection (PAS chercher la plus grande intersection), étant donné la contrainte qu'un ensemble ne peut former une intersection avec un autre ensemble que si au moins les entiers `` x '' se chevauchent. Par exemple, si x = 2, [1,2,3,4] ne peut pas former une intersection avec [1,5,6,7] car il n'y a qu'un seul entier qui se chevauche, pas 2.

Une autre chose à noter (bien qu'évidente) est, pour x=2, si j'ai [1,2,3,4] et [1,2,6,7], l'intersection peut se produire et pour qu'un troisième ensemble forme une intersection, il DOIT avoir { {X3}} quelque part dans l'ensemble.

Je ne suis pas en mesure de former correctement un algorithme pour ce faire, car il existe des moyens exponentiels de comparer les ensembles! Même si je n'avais que 3 ensembles, étant donné la taille de l'ensemble, je devrais considérer chaque comparaison de combinaison de sous-ensembles compte tenu de la contrainte d'intersection.

Je génère mes sets comme suit:

sets = []
for i in range(0,10):
    temp = np.random.randint(1,3000)
    sets.append(set(np.random.randint(1, 3000, temp)))
2
Jonathan 11 mars 2019 à 12:13

2 réponses

Meilleure réponse

Vous pouvez compter le nombre d'occurrences de chaque nombre dans les ensembles. Puisque vous essayez de maximiser le nombre total d'intersections, les nombres les plus courants se traduiront par le plus grand nombre d'intersections possibles (avec le scénario idéal où tous les 2 ensembles forment une intersection). Voici le code pour cela:

import numpy as np

# Set a seed for testing purposes
np.random.seed(1)

# Initialise the min number of elements in an intersection
x = 2

# Initialise the list of sets
sets = list()

# Initialise the count mapping
count = dict()

# Generate the sets
for i in range(0,10):
    temp = np.random.randint(1,3000)
    sets.append(set(np.random.randint(1, 3000, temp)))

# Count each number's occurrence
for s in sets:
    for number in s:
        if number in count:
            count[number] +=1
        else:
            count[number] = 1

# Sort the result (by the count number)
l = sorted(count, key=lambda x: count[x], reverse=True)

# Print the number of occurrences (within the boundary of min x elements)
print(count[l[x-1]])

# Print the numbers that give you the maximum number of intersections
print(l[:x])

Les résultats sont:

7
[2270, 2225]

Dans ce scénario, 7 ensembles sur 10 contiennent les nombres 2270 et 2225, et peuvent donc former un total de 21 (6 * 7/2) intersections. La performance doit être O(NlogN) (en raison du tri) où N est le nombre total de nombres.

1
Kacper Floriański 11 mars 2019 à 10:04

Considérez tous les sous-ensembles de A. (2 ^ 10 sous-ensembles au total)

Ss est un sous-ensemble de A,

Vérifiez l'intersection SI ss, si len (SI)> x, puis mettez à jour le résultat.

Pseudocode:

result = set()

for ss in   all subset:
    SI = ss[0]
    for g in ss:
        SI = SI .intersection(g)
    if len(SI ) >= x:
        result = ss 
print(result)
0
He Xiao 11 mars 2019 à 09:28