Discussion :

[ludovic.fernandez]

Bonjour a tous,

Je souhaite faire une comparaison matricielle entre M et M' afin de savoir si M et une rotation de M' i.e., dans mon cas la rotation ne peut etre que ligne par ligne:

Exemple:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
 
 
(M) =
a b c
b d e
a x y

est egal a :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
 
(M') =
b d e
a b c 
a x y

mais different de :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
 
(M') =
c a b
b d e
a x y

Alors, je vois bien un algorithme tout bete qui prend une ligne de (M) et la compare avec toutes les lignes de M' jusqu'a trouver une identique mais je me demande si ce n'est pas possible d'optimiser cela. De meme, je suis un peu rouille en Maths donc si vous avez les termes adequats pour ce genre de probleme et les meme les notations, merci de me les signaler : j'aime bien savoir ce genre de trucs.

L.

[Tchaill39]

Salut,



Etant donné que tu dois absolument vérifier que les lignes sont les mêmes (pas de permutation de colonne). Afin d'éviter de te taper les test sur les colonnes, transforme une ligne en une chaine de caractère.

a b c
b d e
a x y

A=abc B=bde C=axy

Après tu a juste à vérifier qu'ils sont dans l'ordre. Ca ne change pas grand chose au niveau du poids du calcul mais si tu a des matrices 30*30 les test sont plus pratiques à faire

[ludovic.fernandez]

Merci, j'ai deja serialise mes objets en fait (je ne l'avais pas specifie) donc en definitive et apres reflexion, je dois juste comparer deux matrices colonnes.

On ecrit ca ainsi : (M) = (M)t ?

Donc, si je ne me trompe pas, au lieu de comparer ligne par ligne, il doit y avoir possibilite de comparer les signatures des deux matrices ? Par contre, peut-on calculer une signature sur des objets serialises ?

L.

[millie]

Donc, si je ne me trompe pas, au lieu de comparer ligne par ligne, il doit y avoir possibilite de comparer les signatures des deux matrices ?

Non, une signature est définie pour une permutation, pas pour une matrice.

Edit : ah oui, j'ai compris ou tu voulais en venir, tu définis la permutation

phi(abcdefghi) = defghiadc par exemple. La tu peux déterminer sa signature.

Mais tu peux avoir une permutation qui est de même signature que phi et qui n'est pas du tout une permutation de ligne.

[Nemerle]

Trie les lignes concaténées par ordre lexicographique et concatène. Après tu n'as qu'à comparer 2 chaines!

PS: je ne comprends pas tu parles de "rotation" dans le post initial, cela n'a aucun sens...

[ludovic.fernandez]

Merci Nemerle,

En definitive, c'est exactement ce que je fais mais avec le vocabulaire approprie.

Apres quelques annees sans faire de Maths, j'avoue que permutation et rotation veulent dire la meme chose pour moi. C'est pourquoi, j'exprimais aussi cette volonte de me rafraichir la memoire.

L.