Clusterizzare una matrice booleana

[Silent]

Supponiamo di avere una matrice booleana come la seguente:

Codice:

     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:

     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:

     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 pò 'zozzo' se tradotto in codice.
C'è un modo efficiente per farlo, ad esempio, in Matlab?

Grazie.

[utente__medio]

Ho provato a risolverlo in C++ (con matlab non sono molto pratico, non lo uso da tempo) utilizzando un approccio ricorsivo:

Codice:

#include <iostream>

using namespace std;

const unsigned int R = 5;
const unsigned int C = 7;
bool M[R][C] = {{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}};

void fun_2(int *frutto, int *persona, const unsigned int j, const unsigned int n);

void fun_1(int *frutto, int *persona, const unsigned int i, const unsigned int n)
{
    for(unsigned int j = 0; j < C; ++j)
    {
        if(!persona[j] && M[i][j])
        {
            persona[j] = n;
            fun_2(frutto, persona, j, n);
        }
    }
}

void fun_2(int *frutto, int *persona, const unsigned int j, const unsigned int n)
{
    for(unsigned int i = 0; i < R; ++i)
    {
        if(!frutto[i] && M[i][j])
        {
            frutto[i] = n;
            fun_1(frutto, persona, i, n);
        }
    }
}

int main()
{
    int frutto[R] = {0};
    int persona[C] = {0};
    for(unsigned int i = 0, n = 1; i < R; ++i)
    {
        if(!frutto[i])
        {
            frutto[i] = n;
            fun_1(frutto, persona, i, n++);
        }
    }

    //OUTPUT-----------------------------------
    for(unsigned int i = 0; i < R; ++i)
    {
        for(unsigned int j = 0; j < C; ++j)
        {
            cout << M[i][j] * frutto[i] << " ";
        }
        cout << endl;
    }
}

Questo l'output:

Codice:

0 0 1 0 0 1 0
2 2 0 0 2 0 0
0 0 0 0 0 1 1
0 0 0 0 0 1 0
0 0 0 0 0 1 1

Process returned 0 (0x0)   execution time : 0.023 s
Press any key to continue.


In pratica ho riunito i vari sottoinsiemi in un'unica matrice.

Non so se esistono modi più efficienti per farlo, ma al momento non mi viene in mente altro.


P.S.
Non l'ho testato più di tanto, se riscontri qualche bug fammi sapere.

[Silent]

Proverò, grazie mille per la tua disponibilità

[vict85]

Io lo farei usando un UnionFind (https://en.wikipedia.org/wiki/Disjoint- ... _structure la wiki italiana è poco informativa).

Insomma, fai un union-find sui frutti usando le persone per fare le associazioni. Non è esattamente una struttura immediata da scrivere però e non saprei se ci sono modi semplici per farlo in MATLAB.

[Silent]

Grazie.

[utente__medio]

Proverò, grazie mille per la tua disponibilità

Poi com'è andata, l'hai testato?