Come calcolare la differenza tra due set in C?

Question

Ho due array, diciamo A e B con | A | = 8 e | B | = 4. Voglio calcolare la differenza impostata A-B. Come procedo? Si prega di notare che non ci sono elementi ripetuti in nessuno dei set.

Modifica: Grazie mille a tutti per una miriade di soluzioni eleganti. Dato che sono nella fase di prototipazione del mio progetto, per ora ho implementato la soluzione più semplice raccontata da Brian e Owen. Ma apprezzo l'uso intelligente delle strutture dati come suggerito qui dal resto di voi, anche se non sono uno scienziato informatico ma un ingegnere e non ho mai studiato le strutture dati come un corso. Sembra che sia ora che inizi a leggere CLRS, che sto rimproverando da un po ':) Grazie ancora!

Answer 1

iterare su ogni elemento di A, se ciascuno di questi elementi non sono in B, poi aggiungerli ad una nuova serie C.

Answer 2

Dipende da come si vuole rappresentare il vostro set, ma se sono solo i bit impacchettati possono quindi utilizzare operatori bit a bit, ad es D = A & ~B; darebbe la differenza impostata A-B se i set si adattano a un tipo intero. Per set più grandi è possibile utilizzare matrici di tipi interi e iterare, ad es.

for (i = 0; i < N; ++i) 
{ 
    D[i] = A[i] & ~B[i]; 
} 

Answer 3

array sort A e B
risultato sarà in C
lasciare un - primo elem di A
let b - primo elem di B
quindi:
1) mentre un < b: inserire a in C e a = next elem di A
2) mentre a> b: b = prossimo elem di B
3) se a = b: a = prossimo elem di A eb = prossimo elem di B
4) se b va a finire: inserire r est di A in C e fermare
5) se una va a finire: fermare

Answer 4

Per i set più grandi mi suggeriscono l'ordinamento dei numeri e l'iterazione attraverso di loro emulando il codice a http://www.cplusplus.com/reference/algorithm/set_difference/ che sarebbe O (N log N *), ma poiché le dimensioni dell'insieme sono così piccole, la soluzione fornita da Brian sembra soddisfacente anche se teoricamente è più lenta in O (N^2).

Answer 5

Quanto segue presuppone che gli insiemi siano memorizzati come un contenitore ordinato (come fa std :: set).

C'è un algoritmo comune per unire due elenchi ordinati per produrre un terzo. L'idea è che quando guardi le teste dei due elenchi, puoi determinare qual è il più basso, estrarlo e aggiungerlo alla coda dell'output, quindi ripetere.

Ci sono varianti che rilevano il caso in cui le due teste sono uguali e trattano questo in modo speciale. Impostare intersezioni e unioni sono esempi di questo.

Con una differenza asimmetrica impostata, il punto chiave è che per A-B, quando si estrae la testa di B, la si scartano. Quando estrai la testata di A, la aggiungi all'ingresso a meno che la testa di B sia uguale, nel qual caso lo estrai anche tu e scartalo entrambi.

Sebbene questo approccio sia progettato per strutture di dati ad accesso sequenziale (e archiviazione su nastro, ecc.), A volte è molto utile fare la stessa cosa per una struttura di dati ad accesso casuale, purché sia ​​ragionevolmente efficiente accedervi comunque in modo sequenziale. E non devi necessariamente estrarre le cose per davvero - puoi invece fare copia e passo.

Il punto chiave è che si passano gli input in sequenza, sempre guardando il valore restante più basso successivo, in modo che (se gli input non hanno duplicati) saranno gli elementi corrispondenti. Quindi sai sempre se il tuo prossimo valore più basso da gestire è un oggetto da A senza corrispondenza in B, e l'elemento in B senza corrispondenza in A, o un elemento uguale in A e B.

Più in generale, l'algoritmo per la differenza dell'insieme dipende dalla rappresentazione dell'insieme. Ad esempio, se il set è rappresentato come un vettore di bit, il precedente sarebbe troppo complesso e lento: dovresti semplicemente eseguire il loop dei vettori eseguendo operazioni bit a bit. Se il set è rappresentato come un hashtable (come nel tr1 unordered_set), quanto sopra è sbagliato in quanto richiede input ordinati.

Se si dispone del proprio codice binario che si sta utilizzando per i set, una buona opzione è quella di convertire entrambi gli alberi in elenchi collegati, lavorare sugli elenchi, quindi convertire l'elenco risultante in un albero perfettamente bilanciato. La differenza tra le liste collegate è molto semplice e le due conversioni sono riutilizzabili per altre operazioni simili.

EDIT

della complessità - usando questi algoritmi di unione simile ordine è O (n), a condizione che si può fare i attraversamenti in ordine a O (n). Anche la conversione in una lista e viceversa è O (n) poiché ognuno dei tre passaggi è O (n) - albero-elenco, differenza tra le serie e lista-albero.

Tree-to-list fondamentalmente esegue un attraversamento in profondità, decostruendo l'albero mentre procede. È un trucco per rendere questo iterativo, memorizzare lo "stack" nei nodi gestiti in parte - cambiare un puntatore sinistro-figlio in un puntatore padre appena prima di passare al figlio sinistro. Questa è una buona idea se l'albero può essere grande e sbilanciato.

Convertire una lista in un albero comporta fondamentalmente un attraversamento in profondità di un albero immaginario (basato sulla dimensione, noto dall'inizio) che lo costruisce per davvero mentre si va. Se un albero ha 5 nodi, ad esempio, puoi dire che la radice sarà il nodo 3. Ricorri per costruire un sottoalbero sinistro a due nodi, quindi prendi l'elemento successivo dall'elenco per quella radice, quindi ricorri per costruire un due -nodo sottostruttura destra.

La conversione da elenco a albero non deve essere implementata in modo iterativo: la ricorsività va bene perché il risultato è sempre perfettamente bilanciato. Se non riesci a gestire la profondità di ricorsione del log n, quasi sicuramente non puoi gestire l'albero completo.

Answer 6

Implementare un oggetto impostato in C. È possibile farlo utilizzando una tabella hash per l'archiviazione sottostante. Questo è ovviamente un esercizio non banale, ma esistono alcune soluzioni OpenSource. Quindi devi semplicemente aggiungere tutti gli elementi di A e poi scorrere su B e rimuovere quelli che sono elementi del tuo set.

Il punto chiave è utilizzare la struttura dati corretta per il lavoro.