Collezione di insiemi non contenenti gruppi che sono un sottoinsieme di un altro nella collezione

Question

Sto cercando una struttura dati astratta che rappresenta un insieme di insiemi tali che nessun insieme della collezione è un sottoinsieme di un altro set nella collezione.

Questo significa che sull'inserto saranno soddisfatte le seguenti condizioni:

A. Inserimento di un elemento che è già un sottoinsieme di un altro elemento restituirà la collezione originale.

B. Inserimento di un elemento che è un sovrainsieme di eventuali altri elementi si tradurrà in una collezione con il sovrainsieme aggiunto e le sottoinsiemi rimosso.

Supponendo un ordinamento sugli elementi del set, poi un albero prefisso può essere utilizzato per rappresentare la collezione. Questo permette condizione A da trattare molto rapidamente (vale a dire che non prende più per verificare le condizioni di quello che sarebbe per inserire il sottoinsieme) tuttavia incontrare condizione B richiede tempo.

Mi chiedo se non v'è la struttura dei dati che permette di B da soddisfare rapidamente pure.

Answer 1

L'approccio banale sarebbe quello di mantenere un elenco di gruppi e di effettuare una ricerca lineare attraverso che per ogni set in arrivo (test se l'ingresso è un sottoinsieme).

Questo viene eseguito ovviamente in O (n) tempo per la ricerca lineare e le dimensioni, eventualmente, O (m) per le dimensioni del set in arrivo. Quindi O (n * m) tempo totale (numero di insiemi vs. dimensione di ciascun set).

L'ottimizzazione più evidente, naturalmente, è quello di indice su dimensioni set. Poi si prova solo ogni set entrata contro quelle che sono di dimensioni uguali o superiori. (Un set non può essere un sottoinsieme di qualsiasi insieme più piccolo, duh!).

Il prossimo ottimizzazione che viene in mente è quello di creare nell'indice di elementi. Così per ogni set in entrata che si può trovare l'intersezione di ogni set contenenti ciascuno degli elementi. In altre parole, se, per set entrante {a, b, c}, troviamo che elemento {a} esiste in insiemi A, B e D, elemento {b} esiste in B, E, e F, e {c} esiste in a, B e Z ... allora l'insieme entrante è un sottoinsieme di B (l'intersezione di {a, B, D}, {B, e, F}, e {a, B, Z}).

Quindi, che suona come O (m * log (n)) la complessità a me. (Dobbiamo eseguire ricerche hash su ciascun elemento di ciascun set entrata). Inserimenti dovrebbero anche essere dello stesso ordine (inserendo ID della nuova serie in ciascuna di mappe dell'elemento). (Nell'analisi Big-O 2 * O (m log (n)) si riduce fino a O (m log (n)), ovviamente).

Answer 2

Un'idea banale, che lavorerà a O (K) dove K è stato aggiunto dimensione dell'elemento.

• mantenere set in qualsiasi modo u want
• tenere mappa di set_id -> set_size
• tenere mappa di oggetto -> set_id

A e B sono O (K).

Answer 3

Se i singoli membri della vostra serie A, B, ... sono mappati distinti (e relativamente) numeri primi, e al fianco di ogni set si memorizzano il prodotto di tutti i membri, come p (A), p (B) ecc quindi sottoinsiemi e superset possono essere trovati se p (X) è un fattore di p (Y) o viceversa.

Si potrebbe finire con alcuni numeri molto grandi immagino, ma funziona in teoria.

Ad esempio:

se [a b c d] -> [2 3 5 7], p (abc) = 30, p (abd) = 42, p (bc) = 15, p (abcd) = 210

Answer 4

Che un sito dorky! Ora ho registrato, quindi può a tempo debito in grado di commentare su roba da ieri. Fino ad allora, però ...

@Stephen C: Anche se credo il mio inglese sia adeguata mi sembra di aver acquisito un explicator: ha perso i bit, tuttavia, e il suo commento va letto come segue:

---

  

@Stephen C: trovare i fattori di un   numero arbitrario è infatti NP completo, ma qui non rilevante. Il   questione è se il più piccolo dei due   numeri divide esattamente la più grande, un   operatore modulo semplice. Per esempio,   p (bc) = 15 è un divisore di p (abcd) = 210,   così bc è un sottoinsieme di abcd (come sono insiemi abd   e ABC).

     

Aggiunta di un nuovo insieme S alla raccolta esistente di N insiemi è O (N), assumendo che il confronto e la divisione dei grandi numeri prende approssimativamente allo stesso tempo indipendentemente N.

     

Per ogni esistente ingresso E nella collezione di set, fermata se p (S)   

p (E) e p (E) divide p (S) esattamente. Aggiungere S se si arriva alla fine della raccolta. Un array   di bignum funzionerebbero.

---

@JL:. Se vuoi essere il mio in loco Stalker si prega di sforzarsi di 1) aggiungere valore 2) con precisione