ElectroYou

Supponiamo di avere una matrice booleana come la seguente:

Codice: Seleziona tutto

     0 0 1 0 0 1 0
   
     1 1 0 0 1 0 0
   
     0 0 0 0 0 1 1
   
     0 0 0 0 0 1 0
   
     0 0 0 0 0 1 1


interpretata in questo modo: ogni riga è un frutto e ogni colonna è una persona. Un '1' in posizione (i, j) indica che la persona j vorrebbe mangiare il frutto i.
Vorrei "clusterizzare" questa matrice, creando sottomatrici che indichino sottoinsiemi di persone in competizione per sottoinsiemi di frutti. Nell'esempio sopra vorrei vedere in output:

Codice: Seleziona tutto

     0 0 1 0 0 1 0
   
     0 0 0 0 0 0 0
   
     0 0 0 0 0 1 1
   
     0 0 0 0 0 1 0
   
     0 0 0 0 0 1 1


e

Codice: Seleziona tutto

     0 0 0 0 0 0 0
   
     1 1 0 0 1 0 0
   
     0 0 0 0 0 0 0
   
     0 0 0 0 0 0 0
   
     0 0 0 0 0 0 0


Il modo che viene in mente a me è il seguente algoritmo: partiamo dalla prima riga (primo frutto); scorriamola e annotiamo in una lista quanti '1' incontriamo (persone che lo vogliono); per ognuna di queste persone, percorriamo verticalmente le rispettive colonne segnandoci tutti gli '1' che incontriamo (tutti i frutti desiderati da tutte quelle persone); per ognuno di questi frutti percorriamo orizzontalmente le rispettive righe aggiungendo alla lista di persone precedentemente creata, anche tutte quelle che incontriamo in questo nuovo cammino, e così via...
Mi sembra molto inefficiente e soprattutto un po' 'zozzo' se tradotto in codice.
C'è un metodo efficiente/più pulito per farlo?

Grazie.

La proiezione ortogonale dei vettori che contengono gli 1 nella posizione desiderata per le persone o i frutti sulla matrice stessa (base dello spazio vettoriale) non bastano?

Forse ho capito male il problema, ma se vuoi sapere chi (colonna) è in competizione per mangiare lo stesso frutto (riga), non ti basta analizzare la presenza di più 1 nelle righe e, di conseguenza, rifare la matrice?

Esempio se voglio un sottoinsieme che mi indichi se c'è qualcuno in competizione per mangiare il frutto basterà analizzare la sola riga 3: c'è più di un 1? si, allora il sotto insieme sarà:

Codice: Seleziona tutto

0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 1 1
0 0 0 0 0 0 0
0 0 0 0 0 0 0

Viceversa se voglio sapere se c'è qualcuno in competizione per i frutti e si analizzeranno le righe 3 e 4 e, a mio avviso, il risultato dovrebbe essere identico al precedente perché sul frutto non c'è nessuno in competizione per cui la riga 4 dovrebbe essere tutta a 0 per indicare che non c'è alcuna competizione.

Se invece si vuole comunque sapere se c'è almeno uno che mangia quel determinato frutto, il sotto insieme sarà:

Codice: Seleziona tutto

0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 1 1
0 0 0 0 0 1 0
0 0 0 0 0 0 0

Poi, per la carità, la mia conoscenza booleana non è così approfondita e potrei aver inteso male la problematica, nel caso mi scuso con Ianero per l'intervento inopportuno.

Max

Nella mia ignoranza pensavo alla stessa cosa, se la somma su una riga è >1 c'è competizione.
Ma forse ho inteso male il testo del problema.

Un senso pratico al quesito, ce lo vedrei. E' possibile risolvere tutte le contese con più trattative non interagenti fra loro, o ci vuole per forza una trattativa unica e complessiva? Immaginiamo che si possano stabilire dei conguagli in denaro.