Cos'è ElectroYou | Login Iscriviti

ElectroYou - la comunità dei professionisti del mondo elettrico

Clusterizzare una matrice booleana

Linguaggi e sistemi

Moderatori: Foto UtenteMassimoB, Foto UtentePaolino, Foto Utentefairyvilje

0
voti

[1] Clusterizzare una matrice booleana

Messaggioda Foto UtenteIanero » 10 apr 2022, 19:13

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.
Servo, dai a costui una moneta, perché ha bisogno di trarre guadagno da ciò che impara.
Euclide.
Avatar utente
Foto UtenteIanero
7.814 5 8 13
Master EY
Master EY
 
Messaggi: 4164
Iscritto il: 21 mar 2012, 15:47

0
voti

[2] Re: Clusterizzare una matrice booleana

Messaggioda Foto UtenteIlGuru » 10 apr 2022, 19:49

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?
\Gamma\nu\tilde{\omega}\theta\i\ \sigma\epsilon\alpha\upsilon\tau\acute{o}\nu
Avatar utente
Foto UtenteIlGuru
4.984 2 10 13
G.Master EY
G.Master EY
 
Messaggi: 1775
Iscritto il: 31 lug 2015, 23:32

0
voti

[3] Re: Clusterizzare una matrice booleana

Messaggioda Foto UtenteMax2433BO » 11 apr 2022, 9:07

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 i_2 \; 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 i_2 \; e i_3 si analizzeranno le righe 3 e 4 e, a mio avviso, il risultato dovrebbe essere identico al precedente perché sul frutto i_3 \; 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 Foto UtenteIanero per l'intervento inopportuno.

O_/ Max
Disapprovo quello che dite, ma difenderò fino alla morte il vostro diritto di dirlo [attribuita a Voltaire]

Sapere sia di sapere una cosa, sia di non saperla: questa è conoscenza. [Confucio, "I colloqui"]
Avatar utente
Foto UtenteMax2433BO
15,3k 4 10 13
G.Master EY
G.Master EY
 
Messaggi: 3846
Iscritto il: 25 set 2013, 16:29
Località: Universo - Via Lattea - Sistema Solare - Terzo pianeta...

0
voti

[4] Re: Clusterizzare una matrice booleana

Messaggioda Foto UtenteGioArca67 » 11 apr 2022, 9:57

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.
Avatar utente
Foto UtenteGioArca67
1.605 2 4 7
Master
Master
 
Messaggi: 1495
Iscritto il: 12 mar 2021, 9:36

0
voti

[5] Re: Clusterizzare una matrice booleana

Messaggioda Foto UtenteEcoTan » 11 apr 2022, 10:18

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.
Avatar utente
Foto UtenteEcoTan
6.478 4 11 13
Expert EY
Expert EY
 
Messaggi: 4379
Iscritto il: 29 gen 2014, 8:54


Torna a PC e informatica

Chi c’è in linea

Visitano il forum: Nessuno e 8 ospiti