Ricerca di sottoinsiemi comuni in un elenco di insiemi

0

Diciamo che ho una lista di set, definiti in questo modo (3 set in questo esempio):

A = [1, 2, 3, 4, 5]
B = [4, 5, 6, 7, 8]
C = [1, 2, 3, 4, 5, 6, 7, 8]

Numero totale di elementi definiti nei set: 18

Mi piacerebbe trovare quali sottoinsiemi sono comuni negli insiemi, al fine di semplificare la definizione dei set.

In questo esempio, [4, 5] è comune a tutti i set. Posso facilmente trovarlo applicando un intersezione tra tutti i set. Quindi posso riscrivere la definizione dei set in questo modo:

A, B, C = [4, 5]
A = [1, 2, 3]
B = [6, 7, 8]
C = [1, 2, 3, 6, 7, 8]

Numero totale di elementi: 14

Tuttavia, questo può essere ulteriormente migliorato:

A, C = [1, 2, 3]
B, C = [6, 7, 8]
A, B, C = [4, 5]

Numero totale di elementi: 8

La mia domanda è: c'è qualche algoritmo (pseudocodice) per semplificare la definizione degli insiemi come in questo esempio?

    
posta tigrou 13.10.2014 - 12:21
fonte

1 risposta

1

Ho risposto a una domanda simile a link e l'unica differenza in ciò che ti serve è che la seconda mappa debba mappare un elemento all'insieme di set in cui si trova, piuttosto che a ogni sottoinsieme di quel set.

    
risposta data 13.10.2014 - 17:01
fonte

Leggi altre domande sui tag