Encuentre todos los subconjuntos de la lista de conjuntos que aparecen en al menos N conjuntos diferentes

Estoy trabajando en un algoritmo para agrupar palabras clave del motor de búsqueda por la cantidad de urls que tienen en SERP. Cada grupo representa una url, y cada valor es un id de palabra clave para SERP donde apareció url.


Tengo lista de grupos:

groups = [ [1], [1, 2 ,3], [1, 2, 3, 4, 5], [1, 2, 3 ,4], [2, 3], [4, 5, 6], [4, 5, 7] ] 

Necesito recuperar TODOS los conjuntos de elementos que aparecen al menos en N grupos en orden de “tamaño” disminuye:

En el ejemplo anterior para N = 3 tenemos dos subconjuntos: [1, 2, 3] y [4, 5]


Como veo cómo buscarlo:

Iteración 1: encuentre el conjunto más grande que aparece al menos 3 veces (es [1, 2, 3]) y elimínelo de todos los conjuntos, donde aparece.

Después de la iteración tenemos:

 groups = [ [1], [4, 5], [4], [2, 3], [4, 5, 6], [4, 5, 7] ] 

Iteración 2: encuentre el más grande que aparezca al menos 3 veces (es [4, 5])

Después de la iteración tenemos:

 groups = [ [1], [4], [2, 3], [6], [7] ] 

Fin del algoritmo : porque no hay más conjuntos que aparezcan al menos 3 veces en grupos.


¿Tienes alguna idea para el algoritmo para buscarlos?

N está entre 1 y 10.

La lista de grupos ps es bastante grande, de 1000 a 10000 elementos. Los números son ids de objetos en db.

Aquí hay un enfoque de itertools para la primera parte de lo que ustedes llaman Iteration 1 . Si es posible ejecutarlo, puede ejecutarlo repetidamente en un bucle, eliminando los elementos encontrados en cada etapa. Como indiqué en los comentarios, solo es factible para la pequeña n :

 import itertools def intersect(sets): #forms the intersection of all s in sets #assumes that there is at least one I = sets[0].copy() for s in sets[1:]: I = I & s return I def largestIntersection(sets,n): maxSize = 0 maxSets = [set()] for groupCombo in itertools.combinations(sets,n): I = intersect(groupCombo) if len(I) > maxSize: maxSize = len(I) maxSets = [I] elif len(I) == maxSize: maxSets.append(I) return maxSets 

Por ejemplo:

 >>> groups = [ [1], [1, 2 ,3], [1, 2, 3, 4, 5], [1, 2, 3 ,4], [2, 3], [4, 5, 6], [4, 5, 7] ] >>> groups = [set(group) for group in groups] >>> largestIntersection(groups,3) [{1, 2, 3}] 

En edición: la siguiente modificación podría ayudar, dependiendo de la distribución de los números en los grupos y el tamaño de los grupos:

 def guessSize(sets,n,trials): return max(len(intersect(random.sample(sets,n))) for trial in range(trials)) def maxIntersection(sets,n,trials = 100000): k = guessSize(sets,n,trials) filteredSets = [s for s in sets if len(s) >= k] return largestIntersection(filteredSets,n) 

La idea es reducir primero el número de grupos antes de intentar iterar sobre las intersecciones. Por ejemplo:

 #stress test: import random nums = list(range(1,101)) testGroups = [set(random.sample(nums,random.randint(1,100))) for n in range(1000)] foundGroups = maxIntersection(testGroups,3) 

toma solo unos segundos para calcular foundGroups en lugar de varios minutos si yo hubiera usado directamente la más largestIntersection(testGroups) . Por otro lado, con diferentes opciones de parámetros aleatorios, el ahorro de tiempo se vuelve despreciable.

En la edición adicional: Quizás puedas ser aún más agresivo con el filtrado:

 import collections def maxIntersection(sets,n,trials = 100000): k = guessSize(sets,n,trials) filteredSets = [s for s in sets if len(s) >= k] counts = collections.Counter() for s in filteredSets: for x in s: counts[x] +=1 t = {x for x,c in counts.items() if c >= k} filteredSets = [s & t for s in filteredSets if len(s & t) >= k] return largestIntersection(filteredSets,n) 

Un primer prototipo de aproximación / piratería que combina la belleza de la recursión, la progtwigción pseudo-funcional y las cosas de mi lado. Hay muchas mejoras posibles, especialmente con respecto a los iteradores / listas. Tal vez esto incluso califica como código de espagueti :-).

Advertencia: vea el comentario de @John Coleman con respecto al coeficiente binomial. Estamos generando todos los subconjuntos posibles de valores restantes en cada iteración. Podría mejorarse si los generadores se usan perezosamente (pero aún así no serán factibles para grandes conjuntos de números únicos).

 import itertools groups = [ [1], [1, 2 ,3], [1, 2, 3, 4, 5], [1, 2, 3 ,4], [2, 3], [4, 5, 6], [4, 5, 7] ] def solve(groups, N, sol=[]): if len(groups) == 0: return sol rem_vals = list(set(itertools.chain(*groups))) combs = list(itertools.product(range(2), repeat=len(rem_vals))) combs_ = [[rem_vals[ind] for ind, i in enumerate(combs[comb]) if i] for comb in range(len(combs))] for cand in reversed(sorted(combs_, key=lambda x: len(list(itertools.chain(x))))): if len(cand) == 0: continue else: counter = 0 inds = [] for ind, g in enumerate(groups): if set(cand).issubset(g): counter += 1 inds.append(ind) if counter >= N: sol.append(cand) for i in inds: for j in cand: groups[i].remove(j) return solve(groups, N, sol) return sol print(solve(groups, 3)) 

Salida

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