Newsgroup: it.comp.programmare
Titolo: Analizare una matrice buleana.

Ho una matrice composta da 0 e 1.
Sapete indicarmi degli algoritmi per andare ad individuare quanti sono i
raggruppamenti di 1 e dove si trovano?
Es.:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0  Q
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0  P
0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0  O
0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0  N
0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0  M
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0  L
0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 1 1 0 0 0 0 0 0  I
0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 0 0  H
0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 1 1 1 0 0 0 0 0 0  G
0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 1 1 1 0 0 0 0 0 0  F
0 0 0 0 0 0 1 1 1 0 0 0 0 0 1 1 0 1 0 0 0 0 0 0 0  E
0 0 0 0 1 1 1 0 1 1 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0  D
0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0  C
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  B
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0  A
a b c d e  f  g h  i  j k  l m n o p q r  s  t  u v w x y
Sono presenti 3 gruppi di 1:
Pos(1) = jB
DN(1) = B
UP(1) = E
SX(1) = e
DX(1) = k
Pos(2) = qD
DN(2) = D
UP(2) = L
SX(2) = l
DX(2) = s
Pos(3) = dM
DN(3) = M
UP(3) = O
SX(3) = c
DX(3) = f
---
Outgoing mail is certified Virus Free.
Checked by AVG anti-virus system (
http://www.grisoft.com
).
Version: 6.0.419 / Virus Database: 235 - Release Date: 13/11/02

 raggruppamenti di 1 e dove si trovano?
Non e' un problema banale !
Puoi incontrare parecchi trabocchetti, per esempio, che succede se due
raggruppamenti si "toccano" ? Ne fanno uno solo ?
Prova con un algoritmo di ricerca locale ... :/
Auguri
 Raffaello
P.S.: Se vuoi una risposta precisa e scientifica, prova a postare su
it.scienza.informatica.

 raggruppamenti di 1 e dove si trovano?
Scusa il doppio post, ma mi sono venute a mente 2 cose :
1) Si scrive booleana e non buleana.
2) Che vuoi che venga restituito per questi dati in ingresso ?
1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0
1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0
1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0
1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0
1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0
1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0
1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0
1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
ciao
 Raffaello


Dovrebbe restituire un unico gruppo:
Pos(1) = aA
DN(1) = A
UP(1) = Q
SX(1) = a
DX(1) = y
Ma è un caso un po' limite che non mi dovrebbe mai capitare spero.
Se 2 gruppi si toccano ne formano 1 solo.


 Se 2 gruppi si toccano ne formano 1 solo.
A questo punto devi definire *formalmente* il tuo concetto di gruppo.
facci sapere
 Raffaello

 Raffaello
Un gruppo è un agglomerato di 1 i quali non possono avere attorno a loro
altri 1 che non siano appartenenti allo stesso gruppo. Non possono esistere
gruppi uno dentro l'altro.
Es. di gruppi:
0 0 0 0 0 0 0 0 0 0 0
0 0 0 1 1 1 1 1 0 0 0
0 0 0 1 0 0 0 0 1 0 0
0 0 0 1 0 0 0 0 1 0 0
0 0 0 0 1 1 1 1 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 1 0 0 0 1 0 0 0
0 0 0 1 0 0 0 0 1 0 0
0 0 0 0 1 1 1 1 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 1 1 1 1 1 1 1 0 0
0 0 1 0 0 0 0 0 1 0 0
0 0 1 0 1 1 1 0 1 0 0
0 0 1 0 0 0 0 0 1 0 0
0 0 1 1 1 1 1 1 1 0 0
0 0 0 0 0 0 0 0 0 0 0
2 Gruppi
0 0 0 0 0 0 0 0 0 0 0
0 2 0 1 1 1 1 1 0 0 0
0 2 0 1 1 0 0 0 1 0 0
0 2 0 1 1 1 0 0 1 0 0
0 2 0 0 1 1 1 1 0 0 0
0 2 0 0 0 0 0 0 0 0 0
0 0 1 1 1 1 1 1 1 0 0
2 0 0 0 0 0 0 1 1 0 0
2 2 2 2 2 2 0 1 1 0 0
2 0 0 0 0 0 0 1 1 0 0
0 0 1 1 1 1 1 1 1 0 0
0 0 0 0 0 0 0 0 0 0 0
---


 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0  L
   0 1 2 3 4 5 6 7 8 9 ecc...
riga3: (2, 5)->(13, 15)
riga4: (2, 4)->(14, 14)->(18, 20)
riga5: (3, 5)->(15, 17)->(21, 21)
Confronti la riga3 con la riga4.
(2,5) e (2,4) si toccano quindi li raggruppi.
(2,5) e (14,14) non si toccano quindi è inutile controllare anche (18, 20)
Ora confronti (2,4) con (3,5), ok si toccano e quindi raggruppi anche (3,5)
[il gruppo è diventato {(2,5), (2,4), (3,5) ovviamente ricordanti a che riga
appartengono!].
Confronti anche (2,4) con (15,17), ma non si toccano quindi ti fermi qui.
Alla riga dopo sono tutti zeri, quindi il primo gruppo è finito.
Gli elementi raggruppati dovresti toglierli dalla lista.
Eliminati gli elementi raggruppati la lista appare ora come:
riga3: (13, 15)
riga4: (14, 14)->(18, 20)
riga5: (15, 17)->(21, 21)
Ripeti il procedimento fino a esaurire gli elementi.
(NOTA: confrontato (14, 14) con (15, 17) devi confrontare anche (18, 20) con
(15, 17) comunque queste cose si notano facendo delle prove).
Si potrebbe "linearizzare" un po' l'algoritmo (rendendolo più semplice).
riga3: (2, 5)->(13, 15)
riga4: (2, 4)->(14, 14)->(18, 20)
riga5: (3, 5)->(15, 17)->(21, 21)
Raggruppi tutti gli elementi che si toccano.
Confronti *tutta* la riga 3 con la riga 4 e ottieni:
riga3: (2, 5)->(13, 15)
            |              |
           V            V
riga4: (2, 4)->(14, 14)->(18, 20)
Confronti la riga 4 con la riga 5:
riga3: (2, 5)->(13, 15)
            |              |
           V            V
riga4: (2, 4)->(14, 14)->(18, 20)
           |               |     .-----'  |
          V             V   V         V
riga5: (3, 5)->(15, 17)->(21, 21)
A questo punto trovare i gruppi è facile.
Procedi ricorsivamente!
AddToGroup(element)
{
    for (all_hooked_elements)
    {
        AddToGroup(hooked_element);
    }
}
Per es:
AddToGroup((2, 5));
for (elements hooked to (2,5))
{
    AddToGroup((2,4))
    {
        for (elements hooked to (2,4))
        {
            AddToGroup((3, 5))
            {
                Non ci sono elementi quindi RETURN!
            }
        }
    }
}
E il primo gruppo è fatto.
Secondo gruppo chiamando
AddToGroup((13, 15))
ecc...
Kiuhnm

Grazie ottima idea!!


 migliorare l'algoritmo.
A me la soluzione che hai proposto sembra ottima. Non puoi migliorarla.
Complessita' O(m), lineare. Difatti ogni punto viene preso in
considerazione una volta sola, e al massimo fai 8 confronti per punto.
Congratulazioni.
 Raffaello

 per punto. Congratulazioni.
Meglio cosě. Andavo un po' di fretta e l'algoritmo non l'ho neanche
analizzato :-)
Kiuhnm

 i raggruppamenti di 1 e dove si trovano?
devi considerare la tua matrice come un grafo: i nodi del grafo sono le 
celle che contengono un 1 e per ogni nodo esistono al piu` 4 (o 8, se 
consideri anche le diagonali) archi che lo collegano agli eventuali 1 
adiacenti.
A questo punto per risolvere il problema e` sufficiente individuare le 
componenti connesse del grafo: se cerchi su un qualunque libro di 
algoritmi troverai molto materiale sull'argomento; se non trovi niente 
chiedi pure che cerco di spiegartelo in breve.
Un ultimo consiglio: per rappresentare il grafo non e` necessaria una 
forma esplicita (ad esempio matrice o liste di adiacenza) ma dovrebbe 
bastarne una implicita (anche questa spiegata nei libri di algoritmi)
ciao Anto
-- 
"Computer science is not about computers any more than astronomy
is about telescopes." -- EW Dijkstra