intersezione massima tra n set

Question

Ho set x con elementi y (interi non ordinati) in ciascuno di essi. Voglio trovare la dimensione massima dell'intersezione tra coppia di questo set.

Ad esempio:

* 5 insiemi, size = 3

set 1: 1

impostato 2: 4

set 3: 5 6 7

set 4: 5 8 9

set 5: 5 10 11

intersezione massima hanno impostato 1 con set 2 e la sua dimensione è 2; la risposta è 2.

Quindi, posso farlo in O (x^2 * y) utilizzando HashSets, semplicemente osservando tutte le coppie e calcolando la loro dimensione di intersezione. Ma voglio farlo più velocemente. Penso che ci siano specifici algoritmi o strutture dati che possono aiutare. Puoi darmi qualche idea?

UPDATE: xey è circa 10^3, gli elementi sono int. E non ci sono set uguali.

Answer 1

Un'ottimizzazione che posso pensare è ricordare la dimensione di intersezione tra il primo set e il resto di essi e quindi utilizzare i dati per tagliare alcuni casi.

Come si può utilizzare:

Se avete set A, B, C di lunghezza n e

intersection(A,B) = p 
intersection(A,C) = q 

poi

intersection(B,C) <= n - abs(p - q) 

Per i set nel tuo caso:

S0 = { 1 2 3 } 
S1 = { 4 2 3 } 
S2 = { 5 6 7 } 

di calcolare intersection(S0,S1) = 2 e ricordare il risultato:

[ i(0,1)=2 ] 

poi intersection(S0,S2) = 0, così

[ i(0,1)=2; i(0,2)=0 ] 

E quando sei al computer intersection(S1,S2) dopo aver confrontato primi elementi

(S1[0]=4 != S2[0]=5) 

si può dire che intersection(S1,S2) <= 2 questo è il miglior risultato tu hai finora.

Ciò che può essere ulteriormente migliorato è quello di ricordare risultati più precisi delle intersezioni ma ancora non di computarli tutti.

Non sono sicuro che sia l'opzione migliore. Forse esiste un approccio completamente diverso a questo.

Answer 2

Ecco alcune psuedocodarlo:

function max_intersection(vector<vector<int>> sets): 
    hashmap<int, vector<set_id>> val_map; 
    foreach set_id:set in sets: 
     foreach val in set: 
      val_map[val].push_back(set_id); 
    max_count = 0 
    vector<int> counts = vector<int>(size = sets.size() * sets.size(), init_value = 0); 
    foreach val:set_ids in val_map: 
     foreach id_1:set_id_1 in set_ids: 
      foreach id_2:set_id_2 in set_ids where id_2 > id_1: 
       count = ++counts[set_id_1 * sets.size() + set_id_2]; 
       if (count > max_count): 
        max_count = count; 
    return max_count; 

Quindi, se X è il numero di set e Y è il numero di elementi in ogni set:

1. inserimento in val_map è O(X*Y)
2. Creazione counts e inizializzando ogni elemento a zero è O(X^2)
3. Se non vi sono intersezioni (ogni valore si verifica esattamente una volta), l'ultimo ciclo viene eseguito nel tempo O(X*Y). Tuttavia, all'estremo opposto, se è presente un numero elevato di intersezioni (tutti i set sono equivalenti), l'ultimo ciclo viene eseguito in O(X^2*Y).

Quindi, a seconda della quantità di intersezioni, la complessità temporale è compresa tra O(X*Y + X^2) e O(X^2*Y).

Answer 3

non riesco a pensare a una soluzione che migliorerà O(x*x*y), ma posso suggerire un modo per evitare di hashing e, invece di complessità previstoO(x*x*y) per avere complessità O(x*x*y) al costo di 10^6 memoria aggiuntiva. Osservando i vincoli che hai fornito non avrai più di 10^6 numeri diversi. Quindi la mia idea è la seguente: ordina tutti i numeri e poi li rimuovi (rimuovi i duplicati). Assegna un numero univoco da 1 a 10^6 (o il numero di numeri univoci) a ciascuno dei numeri (utilizzando il loro ordine nell'array ordinato e univoco). Dopo che invece di hashmap su per ogni coppia, usa un set di bit di dimensioni 10^6. In questo modo avrai una certa complessità di O(x*x*y) (come la precomputazione che propongo è di complessità O(x * y *(log(x) + log (y))).