éléments identiques dans une matrice

Version imprimable

29/11/2006, 00h37
isidore

éléments identiques dans une matrice

Bonjour

j'ai une matrice telle que
[ 1 1 1 0
1 1 1 0
1 1 1 0
0 0 0 1]
je travaille sur les graphes connexes/orientés
donc je cherche à détourer
c'est-à dire trouver la matrice carré la plus grande avec des 1 (ici 3*3)
et l'élément restant "1"

auriez vous une piste, ou un ex qui me permettent de déterminer justement cela?
j'ai pensé à flood fill que j'ai vu dans un autre post mais c'est un peu différent, moi c'est des éléments regroupés en forme de matrice carré que je dois trouver.

Merci beaucoup pour votre aide .
29/11/2006, 09h46
sourivore

Si ta matrice ne contient que des entiers tu considère la matrice 1x1 tu multiplies tous les éléments si tu trouves 1 tu continue avec la 2x2 et ainsi de suite.

On n'a pas besoin de parcourir toutes les sous-matrices (pas efficace). On peut faire comme ça :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 i<-1, ok <- vrai Tant que ok et i<=N faire j <- 1 Tant que ok et j <= i faire ok <- tab[i,j]=1 et tab[j,i]=1 j <- j+1 Fin Tant que Si ok alors i <- i+1 Fin Si Fin tant que
En sortie, i est la taille de la plus grande sous-matrice carrée pleine de 1.

29/11/2006, 21h47
isidore

up
30/11/2006, 02h12
isidore

salut

j'ai réussi à faire ce queje voulais en inversant tous les indice en partant du coin en bas à droite cette fois et ensuite j'ai fait parcours un truc uniquement en diagonale (des for avec des i=j)
j'ai éliminé la partie carré haut gauche puis haut droite puis la diagonale

à présent j'ai un autre probleme
si j'ai cela :

0 1 2 3 4 // indices des colonnes
[1 1 0 1 1
1 1 0 1 1
0 0 1 0 0
1 1 0 1 1
1 1 0 1 1]

comment faire en sorte que l'algorithme parcours ces 4 coins?

merci
30/11/2006, 13h08
Nemerle

en fait, tu veux identifier toutes les sous-matrices carrées maximales!

Dans ce cas, pour chaque (i,j) de ta matrice calcule sa valeur k[i,j] tel que la diagonale

Citation:

(XI[i,j],XJ[i,j]) --> (XI[i,j]+k[i,j],XI[i,j]+k[i,j])

est celle du sous-carré maximal contenant (i,j). Pour cela tu adapte ton algo actuel autour de (i,j).

Avec les k[i,j], tu fais ce que tu veux: les valeurs maximales par exemple te permettent de trouver simplement les plus grand carrés:
- tu prends un tel k maximal,
- tu prends un (i,j) tel que k[i,j]=k pour obtenir le carré maximal (de diagonale (XI[i,j],XJ[i,j]) --> (XI[i,j]+k[i,j],XI[i,j]+k[i,j]) ), et tu fais

Citation:

k[a,b]=-1 pour tous XI[i,j]<=a<=XI[i,j]+k et tout XJ[i,j]<=b<=XJ[i,j]+k

- et tu recommences...

une solution en C++

Citation:

Envoyé par isidore

Bonjour

j'ai une matrice telle que
[ 1 1 1 0
1 1 1 0
1 1 1 0
0 0 0 1]
je travaille sur les graphes connexes/orientés
donc je cherche à détourer
c'est-à dire trouver la matrice carré la plus grande avec des 1 (ici 3*3)
et l'élément restant "1"

auriez vous une piste, ou un ex qui me permettent de déterminer justement cela?
j'ai pensé à flood fill que j'ai vu dans un autre post mais c'est un peu différent, moi c'est des éléments regroupés en forme de matrice carré que je dois trouver.

Merci beaucoup pour votre aide .

Essayez ça en corrigeant éventuellement qq erreurs

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
#include <iostream>
# include <stdlib.h>
 
// pour représenter des matrices d'entiers binaires
class MatInt
{
private:
    int n; // l'ordre
    int * coeffs; // les coefficients entiers
public:
// constructeurs
    MatInt()// matrice d'ordre 1 nulle par défaut
    {
        n=1;
        coeffs=new int[1];
        coeffs[0]=0;
    }
    MatInt (int u)// constructeur à partir du rang sans initialisation
    {
        n=u;
        coeffs= new int[n*n];
    }
    MatInt( int u, int T[]) // constructeur avec initialisation (on suppose que T est de dim n*n
    { n=u;
        coeffs=T;
    }
    MatInt(int i, int j,int t, MatInt * A)// fabrique le mineur d'ordre t de la matrice
    // pointée par A commençant à la ligne i et à la colonne j
    {n=t;
        coeffs=new int[t*t];
        int u,v,w;
        for (u=0; u<t;u++)
        {
            for (v=0;v<t;v++)
            {
                w=(i+u)*A->n+j+v;
                coeffs[u*t+v]=A->coeffs[w];
            }
        }
    }
// Entrées sorties
    void show()
    {
        std::cout<<"\n";
        for (int i=0;i<n;i++)
        {
            for (int j=0; j<n;j++)
                std::cout<<coeffs[i*n+j];
            std::cout<<"\n";
        }
        std::cout<<"\n";
    }
 
// Test matrice pleine (que des 1)
    bool IsFull()
    {
        for (int i=0; i<n*n;i++)
            if (!coeffs[i]) return false ;
        return true;
    }
// détermine la taille du plus gros bloc plein dans la matrice
    int rang ()
    {
        int r=0;
        MatInt * M;
        for (int t=1; t<=n;t++)
            for (int i=0;i<n-t;i++)
                for (int j=0;j<n-t;j++)
                {
                    M=new MatInt(i,j,t,this);
                    if (M->IsFull()) r=t; // mise à jour du max
                    delete M;
                }
        return r;
    }
 
// destructeur
    virtual ~MatInt()
    {
        delete coeffs;
    }
    ; // destructeur virtuel just in case ....
 
};
 
 
 
 
 
 
int main()
{
    int T[]={1 ,1,0,1,1,0,0,0,1};
    MatInt A(3,T);
    MatInt B(0,0,2,&A);
    MatInt C(1,1,2,&A);
    A.show();
    std::cout<<B.IsFull();
    std::cout<<"\n";
    std::cout<<C.IsFull();
    std::cout<<"\n";
    std::cout<<A.rang();
    std::cout<<"\n";
    return 0;
}

merci pour vos réponses.

Zavonen, j'ai eu un problème avec ton code et puis je code en langage C.
Nemerle je n'ai rien compris:oops:

je travaille sur les graphe connexes donc je trouver toutes les sous matricé carré maximale (ainsi que + tard les indices de colonne et ligne à retenir)

voilà où j'en suis :

j'ai une matrice telle que :
{1,0,1,1,1},
{0,1,1,0,1},
{0,1,1,0,0},
{1,1,0,1,1},
{1,1,0,1,1}
je dois trouver les sous matrices carré.

je vais m'intéresser au carré 3*3 en haut à gauche
dans mon programme, pour déjà repérer où j'avais réussi à détecter des matrices carré j'ai changer les valeurs et mis à 3.
je travaille avec des tableau dynamique donc normalement je ne sais pas à l'avance sur quel genre de matrice je tomberai.

Dans mon programme, avec z=1, j'obtiens :
1 0 1
0 3 3
0 3 3
donc ça marche.
par contre avec z=0, j'obtiens :
3 3 1
3 3 1
0 0 1
les chiffres en magenta ne devraient pas etre modifié dans mon programme

en fait le z désigne le coin de départ.
for (S=z;S<2;S++) //for (S=0;S<((5/2)-1);S++)
ici c'est le chiffre 2 qui désigne où s'arreter.

si ma matrice est 1 1 1; 1 1 1; 0 1 1 alors il me faut z=0
pour ma matrice 1 0 1; 0 1 1; 0 1 1 il me faut z=1
et je n'arrive pas à modifier, comment faire??

je me suis servi de l'algo de borisd

mon programme est le suivant actuellement :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 #include <stdio.h> #include <iostream.h> #include <stdlib.h> #include <malloc.h> void main() { int nb_sommets; nb_sommets = 5; /*int matrice_adj[4][4]={ {1,1,1,1}, {1,1,1,1}, {1,1,1,1}, {0,0,0,1} };*/ int matrice_adj[5][5]={ {1,0,1,1,1}, {0,1,1,0,1}, {0,1,1,0,0}, {1,1,0,1,1}, {1,1,0,1,1} }; // printf("%d\n", matrice_adj[3][3]); int z=0; // agir sur S ou z int i=z; int j,S; int ok=1; int compteur=0; while (ok && i<nb_sommets) { for (S=z;S<2;S++) //for (S=0;S<((5/2)-1);S++) { j=S; while (ok && j<=i) { ok=(matrice_adj[i][j]==1 && matrice_adj[j][i]==1); // cout<<"ok="<<ok<<"et i="<<i<<"et j="<<j<<endl; if (ok==0) {compteur++; //cout<<compteur<<endl; for (int k = S; k < i;k++) { for (int m = S; m < i;m++) { //if (k!=m) { {matrice_adj[k][m]=3; matrice_adj[m][k]=3; } } } } } j=j+1; } if (ok) { i=i+1; } } } // fonction affichage de la matrice que je devrai enlever { int i,j; for (i = 0; i < nb_sommets;i++) { for (j = 0; j < nb_sommets;j++) { cout<<matrice_adj[i][j]<<" "; } cout<<endl; } } }
(j'avais prévu de parcourir de 0 à 2 ou 3 (je sais pas) puis en inversant tous les indices de 5 à 2 ou 3 et de compter les 1 sur la diagonale restante.
c pour cela que là j'étudie avec que le coté haut gauche de la matrice.

Merci pour votre aide.

11/12/2006, 21h02
Nemerle

Citation:

Envoyé par Nemerle

en fait, tu veux identifier toutes les sous-matrices carrées maximales!

Dans ce cas, pour chaque (i,j) de ta matrice calcule sa valeur k[i,j] tel que la diagonale

Citation:

(XI[i,j],XJ[i,j]) --> (XI[i,j]+k[i,j],XI[i,j]+k[i,j])

est celle du sous-carré maximal contenant (i,j). Pour cela tu adapte ton algo actuel autour de (i,j).

La plus grande matrice carré contenant (i,j), tu vois ce que c'est? Son élément "en haut à gauche" a pour coordonnées disons (a,b), et son élément "en bas à droite" (c,d). Si tu notes k le nombre d'éléments sur la diagonal de cette plus grande matrice carré, en fait c=a+k et d=b+k. Ok?

Ma notation est XI[i,j]=a, XJ[i,j]=b et k[i,j]=k. C'est bon?

Citation:

Envoyé par Nemerle

Avec les k[i,j], tu fais ce que tu veux: les valeurs maximales par exemple te permettent de trouver simplement les plus grand carrés:
- tu prends un tel k maximal,
- tu prends un (i,j) tel que k[i,j]=k pour obtenir le carré maximal (de diagonale (XI[i,j],XJ[i,j]) --> (XI[i,j]+k[i,j],XI[i,j]+k[i,j]) ), et tu fais

Citation:

k[a,b]=-1 pour tous XI[i,j]<=a<=XI[i,j]+k et tout XJ[i,j]<=b<=XJ[i,j]+k

- et tu recommences...

Ca veux dire qu'une fois que tu a calculé tous les XI[i,j], XJ[i,j] et les k[i,j] (que tu stockes), tu cherches la plus grande valeur MAX des k, puis tu cherches dans ta matrice k[i,j] la valeur MAX --> sa position te donne un couple (i,j). La plus grande matrice carré (donnée par XI[i,j] et XJ[i,j] et MAX) est ta 1iere matrice "maximale" !!! Et tu continues...