[c++] Insiemi e disposizioni

[dileoa]

Vorrei sottoporvi un problema che sto studiando in questo periodo per vedere se qualcuno può darmi una dritta su un algoritmo di soluzione. Il problema è il seguente:
"Ho un insieme di A di n elementi (numeri interi) e n suoi sottoinsiemi (A1, A2, ..., An). Devo trovare un sottoinsieme X di A costituito da k elementi (k<n) tale per cui esistono k sottoinsiemi tra A1, A2, ..., An che sono anche sottoinsiemi di X."
Mi rendo conto che così enunciato si capisca ben poco, allora ecco un esempio pratico:
dato l'insieme A={1,2,4,5,6,7,8,9} e gli 8 sottoinsiemi di A, {5,7,9},{1,4,5,7},{1,4,5,6},{2,7},{1,8},{2,5,9},{2,5},{6,8}, esiste un sottoinsieme X di A {2,5,7,9} tale per cui:
- {2,5,7,9} è composto di 4 elementi;
- i 4 quattro sottoinsiemi di A {5,7,9},{2,7},{2,5,9},{2,5} sono anche sottoinsiemi di {2,5,7,9}.
La soluzione che mi è venuta in mente è di confrontare tutti i possibili sottoinsiemi di A di k elementi [pari a n!/(n-k)!] con i sottoinsiemi A1, A2, ..., An finche non ne trovo uno che verifichi la condizione. Tuttavia questo attacco a forza bruta mi sembra poco elegante. Qualcuno può suggerirmi una soluzione migliore?
Grazie
Antonio

[wingman87]

Una domanda: se nel tuo esempio oltre agli 8 sottoinsiemi che hai scritto ce ne fosse stato un nono, {2,9} ad esempio, (e quindi) un altro sottoinsieme dell'insieme soluzione, la soluzione data sarebbe comunque corretta?
A livello logico direi di sì, però preferirei una conferma.
Ancora una domanda: quanto sono grandi gli insiemi su cui dovresti lavorare?

[dileoa]

La risposta è no: il numero di elementi del sottoinsieme X deve essere uguale al numero di sottoinsiemi di A inclusi in X, anche se non è detto che il problema abbia soluzioni, ossia, per taluni insiemi A e relativi sottoinsiemi A1, A2, ..., An, X potrebbe non esistere. Inoltre il numero di sottoinsiemi di A è sempre uguale al numero di elementi di A.
Il numero massimo di elementi di A è < di 9.
Grazie
Antonio

[cionci]

Ti prendi gli n sottoinsiemi, ti crei una matrice n x n che rappresenti gli n sottoinsiemi.
Metti un mark in [x][y] se l'elemento y è contenuto nell'insieme x.
Diventa automatico che dovrai scegliere fra gli elementi che sono meno rappresentati negli insiemi, ricordandoti che ti porterai dietro anche gli altri elementi appartenenti agli insiemi che contengono l'elemento scelto.