Informatica I - gli insiemi e le operazioni con gli insiemi

Insieme (set)

È un contenitore (eventualmente vuoto) di oggetti distinti (cioè non contiene duplicati). In un insieme useremo i seguenti metodi:

• Inserimento di un oggetto (fallisce silenziosamente se l’oggetto è già presente).
  Sintassi: public interface Set extends Container { void add(Object obj); }
• Verifica della presenza di un oggetto: boolean contains(Object obj);
• Ispezione di tutti gli oggetti (restituisce un array di riferimenti agli oggetti dell’insieme): Object[] toArray();

Non definiamo un’operazione di rimozione; useremo l'operazione di sottrazione tra insiemi.

Operazioni sugli insiemi

• A ∪ B: Unione, appartengono all’unione di due insiemi tutti e soli gli oggetti che appartengono ad almeno uno dei due insiemi.
• A ∩ B: Intersezione, appartengono all’intersezione di due insiemi tutti e soli gli oggetti che appartengono ad entrambi gli insiemi.
• A - B (oppure anche A \ B): Sottrazione, appartengono all’insieme sottrazione tutti e soli gli oggetti che appartengono ad A e non appartengono a B. Non è necessario che B sia un sottoinsieme di A.

Unione

public static Set union(Set s1, Set s2) {
    Set x = new ArraySet();
    // Inseriamo gli elementi del primo insieme
    Object[] v = s1.toArray();
    for (int i = 0; i < v.length; i++)
        x.add(v[i]);
    // Inseriamo tutti gli elementi del secondo insieme, sfruttando le proprietà di add (niente duplicati...)
    v = s2.toArray();
    for (int i = 0; i < v.length; i++)
        x.add(v[i]);
    return x;
}

Se contains è O(n) (e, quindi, lo è anche add), questa operazione è O(n²).

Intersezione

public static Set intersection(Set s1, Set s2) {
    Set x = new ArraySet();
    Object[] v = s1.toArray();
    for (int i = 0; i < v.length; i++)
        if (s2.contains(v[i]))
            x.add(v[i]);
    return x;
}

Se contains è O(n), l’operazione di intersezione è O(n²).

Sottrazione

public static Set subtract(Set s1, Set s2) {
    Set x = new ArraySet();
    Object[] v = s1.toArray();
    for (int i = 0; i < v.length; i++)
        if (!s2.contains(v[i]))
            x.add(v[i]);
    return x;
}

Se contains è O(n), l’operazione di sottrazione è O(n²).

Insieme con array non ordinato

Riassumendo, realizzando un insieme con un array non ordinato:

• Le prestazioni di tutte le operazioni primitive dell’insieme sono O(n).
• Le prestazioni di tutte le operazioni che agiscono sugli insiemi complessi sono O(n²).