Partage

Extraction de sous matrice carré dans une matrice

Sujet résolu

19 avril 2018 à 15:48:41

Bonjour chers tous,

Je cherche à extraire des sous matrices carré dans une matrice donnée. Supposons l’exemple sur l'mage en PJ. Je cherche à considérer les sous matrices en rayures.

Merci pour vos suggestions.

hamster1er

19 avril 2018 à 16:46:46

Salut,

En bourinant : parcours toute la matrice et fais un test sur les indices (il y a peut être des trucs à faire modulo 3)

Après si c'est forcément des sous matrices 3x3 réparties régulièrement sur la diagonale, tu le programme en dur, t'as que 9 éléments à écrire. Et ensuite tu peux boucler sur les sous matrices.

Par exemple :

for (int SM = 0; SM< nbSM; SM++){
dstMat[SM](0,0)=srcMat(3*SM,3*SM);
dstMat[SM](0,1)=srcMat(3*SM,3*SM+1);
dstMat[SM](0,2)=srcMat(3*SM,3*SM+2);
dstMat[SM](1,0)=srcMat(3*SM+1,3*SM);
dstMat[SM](1,1)=srcMat(3*SM+1,3*SM+1);
...
// SM pour Sous Matrice, nbSM le nombre de SM que tu veux tirer, dstMat[SM] tes matrices de destinations, srcMat ta matrice de base
 }

( la syntaxe dstMat[i](j,k) c'est probablement pas bon hein. ça dépend comment tu fais les choses et avec quoi)

Sinon il y a peut être des méthodes plus intelligentes déjà codées dans des bibliothèques de math (genre Eigen ou équivalent...)

-
Edité par hamster1er 19 avril 2018 à 16:51:58

koala01

19 avril 2018 à 17:19:54

Salut,

Tu as été en mesure de tracer ton dessin. Tu as donc, d'une manière ou d'une autre, été en mesure de déterminer les cases de ta matrice qui devaient être hachurées.

Pourquoi n'essayerais tu pas dans un premier temps d'exprimer clairement (en français) la logique que tu as suivie pour y arriver?

Cela pourrait prendre une forme proche de
Pour la première sous matrice, j'ai pris les cases qui se dans l'intervalle [XXX, YYY[ pour la ligne et dans l'intervalle [AAA,BBB[ pour la colonne
Pour la seconde sous matrice, j'ai... (pareil)
...
Pour la Nième sous matrice j'ai ... (pareil)

Une fois que ce sera fait, tu devrais *** assez facilement *** pouvoir déterminer la relation qui existe entre les différents intervalles que tu as trouvés, et, partant de là, tu devrais pouvoir trouver une "formule mathématique" qui te permettra de les représenter.

Une fois que tu auras cette formule, tu devrais pouvoir mettre en place un algorithme qui te permettra de faire ce que tu souhaites, et que tu devrais pouvoir vérifier et valider à l'aide de ton dessin

Quand tu auras l'algorithme en question, tu n'auras "plus qu'à" le reproduire avec le langage de programmation que tu souhaites utiliser. Mais ca, ce ne sera plus qu'un "long et fastidieux travail de dactylographie"

Ce qui se conçoit bien s'énonce clairement. Et les mots pour le dire viennent aisément.Mon nouveau livre : Coder efficacement - Bonnes pratiques et erreurs à éviter (en C++)Avant de faire ce que tu ne pourras défaire, penses à tout ce que tu ne pourras plus faire une fois que tu l'auras fait

AziseDIALLO

20 avril 2018 à 10:16:29

hamster1er a écrit:

Salut,

En bourinant : parcours toute la matrice et fais un test sur les indices (il y a peut être des trucs à faire modulo 3)

Après si c'est forcément des sous matrices 3x3 réparties régulièrement sur la diagonale, tu le programme en dur, t'as que 9 éléments à écrire. Et ensuite tu peux boucler sur les sous matrices.

Par exemple :
for (int SM = 0; SM< nbSM; SM++){
dstMat[SM](0,0)=srcMat(3*SM,3*SM);
dstMat[SM](0,1)=srcMat(3*SM,3*SM+1);
dstMat[SM](0,2)=srcMat(3*SM,3*SM+2);
dstMat[SM](1,0)=srcMat(3*SM+1,3*SM);
dstMat[SM](1,1)=srcMat(3*SM+1,3*SM+1);
...
// SM pour Sous Matrice, nbSM le nombre de SM que tu veux tirer, dstMat[SM] tes matrices de destinations, srcMat ta matrice de base
 }
( la syntaxe dstMat[i](j,k) c'est probablement pas bon hein. ça dépend comment tu fais les choses et avec quoi)

Sinon il y a peut être des méthodes plus intelligentes déjà codées dans des bibliothèques de math (genre Eigen ou équivalent...)

-
Edité par hamster1er il y a environ 16 heures

Bonjour koala01 et hamster1er,

Merci pour vos réponses rapides.

Je suis tout à fait d'accord avec vous. Je cherche à trouver une formule générale à mon problème. L'exemple dans l'image n'est qu'une illustration simplifiée du problème.

Alors pour être plus explicite, considérons une matrice M² quelconque. Les lignes et les colonnes représentent différents types d'éléments identiques consécutifs : A1, A2,..., An; B1, B2,...,Bp; ...; Z1, Z2,...Zz. Ce que je cherche à faire c'est de considérer uniquement les sous matrices représentant chaque type d'élément identique. En d'autres termes je doit extraire autant de sous matrices qu'il y ait de type d'éléments (Par exemple 4 dans le cas de ma figure).

Pour l'instant, j'ai pu résoudre le cas où n=p=...=z mais sans vraiment une formule mathématique explicite.

Voila un peu. je sais si j'ai été un plus clair!!!

-
Edité par AziseDIALLO 20 avril 2018 à 10:21:09

hamster1er

20 avril 2018 à 14:45:23

C'est à dire, si j'ai bien compris : une matrice carrée "presque quelconque", les éléments à récupérer peuvent être regroupés le long de la diagonale sous forme de rectangles de dimensions quelconque...

C'est un peu la me****.

Ce que je ferai, c'est que je parcourrais la diagonale dans une boucle do-while.

Tu démarres à l'élément (0,0) ensuite tu regardes les éléments à droite (0,0+m), puis les élément en dessous (0+n,0). Dès que la valeur des éléments change, ça te donne m et n. Tu peux récupérer une première sous matrice.

Ensuite tu repars à l'exploration, en partant de l'élément de la diagonale "qui va bien". Par contre je peux pas t'aider à définir "qui va bien", ça dépend de ton problème et de ta matrice.

Au hasard, je repartirai de l’élément [ max(m,n) , max(m,n) ]

Il va te falloir un bon paquet d'indices, et l'algo que je décris a une complexité un peu naze ( il te faut au moins 3 sous-boucles dans le while... On a déjà fait mieux niveau complexité lol)

AziseDIALLO

20 avril 2018 à 16:06:31

hamster1er a écrit:

C'est à dire, si j'ai bien compris : une matrice carrée "presque quelconque", les éléments à récupérer peuvent être regroupés le long de la diagonale sous forme de rectangles de dimensions quelconque...

C'est un peu la me****.

Ce que je ferai, c'est que je parcourrais la diagonale dans une boucle do-while.

Tu démarres à l'élément (0,0) ensuite tu regardes les éléments à droite (0,0+m), puis les élément en dessous (0+n,0). Dès que la valeur des éléments change, ça te donne m et n. Tu peux récupérer une première sous matrice.

Ensuite tu repars à l'exploration, en partant de l'élément de la diagonale "qui va bien". Par contre je peux pas t'aider à définir "qui va bien", ça dépend de ton problème et de ta matrice.

Au hasard, je repartirai de l’élément [ max(m,n) , max(m,n) ]

Il va te falloir un bon paquet d'indices, et l'algo que je décris a une complexité un peu naze ( il te faut au moins 3 sous-boucles dans le while... On a déjà fait mieux niveau complexité lol)

C'est exactement ça oui

Tout à fait d'accord avec toi. C'est un peu de la bouillie tout ça.

vector<int> Ligne;
vector<int> Colonne;
for (int i = 0; i < nbElements; i += nbCopies) {
    for (int j = 0; j < nbCopies; j++ ) {
	Ligne.push_back(i);				 
        Colonne.push_back(i+nbCopies);
    }

}

for (int l = 0; l < nbElements; l++) {
	int c = 0;
	while (c < nbElements)
	{
				if (c == Ligne.at(l)) {
					while (c < Colonne.at(l)) {
						//Sous matrices de la diagonale
						c++;
					}
				}
				else {
					// Elements hors sous matrices de la diagonale
					c++;
				}
				
			}

		}

Ci-dessus mon code pour le cas où les matrices de la diagonale ont la même taille. Comme je le disais, il manque encore un peu d’esthétique et de l'optimisation derrière.

En tout cas merci pour tes suggestions et remarques très pertinentes!!!

Deedolith

20 avril 2018 à 16:43:57

Tu as 2 problématiques:
1) Extraire une sous-matrice.
2) Realiser plusieurs extractions.

sur la première, d'un point de vue générique, il n'y a pas 36 solutions:
Tu fournis des coordonnées de départ, de fin, et tu recopie tout ce qu'il y a entre les deux.
L'implémentation dépendra de tes choix d'architecture, par exemple si l'on se base sur la classe Matrix préférée de Ksass'Peuk, et en représentant les coordonnées sous forme de paire, cela peut donner quelque chose comme suit:

template<class T>
class Matrix
{
private:
    std::size_t mWidth;
    std::size_t mHeight;
    std::vector<T> mDatas;
public:
    Matrix(std::size_t width, std::size_t height, T const& t = T{});
    Matrix(Matrix const& m)                 = default;
    Matrix& operator=(Matrix const& m)      = default;
    T const& operator()(std::size_t x, std::size_t y) const;
    T& operator()(std::size_t x, std::size_t y);
    std::size_t width() const;
    std::size_t height() const;
};

Matrix<int> extract(Matrix<int> const& source, std::pair<size_t, size_t> const& start, std::pair<size_t, size_t> const& end);
void display(Matrix<int> const& in);

int main()
{
        // instanciation et remplissage de la source
    Matrix<int> source(6, 6);
    for(size_t i = 0; i < source.width(); ++i)
    {
        for(size_t j = 0; j < source.height(); ++j)
            source(i, j) = i + i * j;
    }
    display(source);
    std::cout << "\n----------------------------" << std::endl;
        // extraction arbitraire
    Matrix<int> cible = extract(source, std::pair<size_t, size_t>{1, 1}, std::pair<size_t, size_t>{3, 3});
    display(cible);

}

Matrix<int> extract(Matrix<int> const& source, std::pair<size_t, size_t> const& start, std::pair<size_t, size_t> const& end)
{
    Matrix<int> cible(end.first - start.first, end.second - start.second);
    for(size_t i = start.first; i < end.first; ++i)
    {
        for(size_t j = start.second; j < end.second; ++j)
        {
            cible(i - start.first, j - start.second) = source(i, j);
        }
    }
    return cible;
}

void display(Matrix<int> const& in)
{
    for(size_t i = 0; i < in.width(); ++i)
    {
        for(size_t j = 0; j < in.height(); ++j)
            std::cout << "[" << in(i, j) << "]";
        std::cout << "\n";
    }
}

Quand à la seconde problématique, elle peut être réalisée avec une simple boucle:

for(size_t i = 0; i < 3; ++i)
{
    std::cout << "\n----------------------------" << std::endl;
    Matrix<int> cible = extract(source, std::pair<size_t, size_t>{i*2, i*2}, std::pair<size_t, size_t>{i*2 + 2, i*2 + 2});
    display(cible);
}

Enfin, si c'est à la classe Matrix de fournir le service d'extraction, vu que les données sont linéarisées et stockées dans un vector, on peut tirer avantage de l'un des constructeur de recopie du vector:

std::vector<int> input{10, 5};
    // extraction du 3e au 5e element.
std::vector<int> output{input.begin() + 2, input.begin() + 5};

AziseDIALLO

21 avril 2018 à 23:33:42

Deedolith a écrit:

Tu as 2 problématiques:
1) Extraire une sous-matrice.
2) Realiser plusieurs extractions.

template<class T>
class Matrix
{
private:
    std::size_t mWidth;
    std::size_t mHeight;
    std::vector<T> mDatas;
public:
    Matrix(std::size_t width, std::size_t height, T const& t = T{});
    Matrix(Matrix const& m)                 = default;
    Matrix& operator=(Matrix const& m)      = default;
    T const& operator()(std::size_t x, std::size_t y) const;
    T& operator()(std::size_t x, std::size_t y);
    std::size_t width() const;
    std::size_t height() const;
};

Matrix<int> extract(Matrix<int> const& source, std::pair<size_t, size_t> const& start, std::pair<size_t, size_t> const& end);
void display(Matrix<int> const& in);

int main()
{
        // instanciation et remplissage de la source
    Matrix<int> source(6, 6);
    for(size_t i = 0; i < source.width(); ++i)
    {
        for(size_t j = 0; j < source.height(); ++j)
            source(i, j) = i + i * j;
    }
    display(source);
    std::cout << "\n----------------------------" << std::endl;
        // extraction arbitraire
    Matrix<int> cible = extract(source, std::pair<size_t, size_t>{1, 1}, std::pair<size_t, size_t>{3, 3});
    display(cible);

}

Matrix<int> extract(Matrix<int> const& source, std::pair<size_t, size_t> const& start, std::pair<size_t, size_t> const& end)
{
    Matrix<int> cible(end.first - start.first, end.second - start.second);
    for(size_t i = start.first; i < end.first; ++i)
    {
        for(size_t j = start.second; j < end.second; ++j)
        {
            cible(i - start.first, j - start.second) = source(i, j);
        }
    }
    return cible;
}

void display(Matrix<int> const& in)
{
    for(size_t i = 0; i < in.width(); ++i)
    {
        for(size_t j = 0; j < in.height(); ++j)
            std::cout << "[" << in(i, j) << "]";
        std::cout << "\n";
    }
}

Quand à la seconde problématique, elle peut être réalisée avec une simple boucle:

for(size_t i = 0; i < 3; ++i)
{
    std::cout << "\n----------------------------" << std::endl;
    Matrix<int> cible = extract(source, std::pair<size_t, size_t>{i*2, i*2}, std::pair<size_t, size_t>{i*2 + 2, i*2 + 2});
    display(cible);
}

std::vector<int> input{10, 5};
    // extraction du 3e au 5e element.
std::vector<int> output{input.begin() + 2, input.begin() + 5};

Bonjour Deedolith,

C'est effectivement mes problematiques.

Merci a toi pour tes explications et l'implementation qui va avec.

Je pense disposer assez d'elements maintenant pour mettre mon sujet en "Resolu".

Merci encore a tous...