Algorithme sur des "Demi-diagonales" de matrices
Bonjour à tous,et désolé par avance pour la longueur de mon post, elle est due à mes dessins d'illustration.
Dans un algorithme j'obtiens des matrice d'ordre n (avec n pair). Ces matrices sont définies uniquement pour le triangle supérieur et ne peuvent contenir que des 0 et des 1.
Par exemple:
_ _ _ _ _ _
|0 1 0 0 0 1
|0 0 0 1 1 0
|0 0 0 0 1 0
|0 0 0 0 1 0
|0 0 0 0 0 0
|0 0 0 0 0 0
Ou dans un cas général avec x = 0 ou 1 et n = 8.
col 0 1 2 3 4 5 6 7
lin _ _ _ _ _ _ _ _
0 |0 X x x x x x x
1 |0 0 x x x x x x
2 |0 0 0 x x x x x
3 |0 0 0 0 x x x x
4 |0 0 0 0 0 x x x
5 |0 0 0 0 0 0 x x
6 |0 0 0 0 0 0 0 x
7 |0 0 0 0 0 0 0 0
On a le droit de changer DE LA MÊME MANIÈRE l'ordre des lignes et des colonnes.
Par exemple on peux avoir:
col 0 3 1 2
lin _ _ _ _
0|
3|
1|
2|
mais pas
col 0 1 3 2
lin _ _ _ _
0|
3|
1|
2|
(car les lignes font 0132 != colonnes 0312).
Enfin ce que j'appelle demi-diagonale (je ne connais pas le nom de ceci, si tenté que ça en ait un) est : aij tel que i = n/2+k et j = k avec k<n/2.
Si n = 8, elle est notée avec des x
col 0 1 2 3 4 5 6 7
lin _ _ _ _ _ _ _ _
0 |0 0 0 0 x 0 0 0
1 |0 0 0 0 0 x 0 0
2 |0 0 0 0 0 0 x 0
3 |0 0 0 0 0 0 0 x
4 |0 0 0 0 0 0 0 0
5 |0 0 0 0 0 0 0 0
6 |0 0 0 0 0 0 0 0
7 |0 0 0 0 0 0 0 0
Voila, j'ai enfin tout défini!
Je cherche à un algo qui me permettrait de savoir combien on peut mettre de 1 au maximum sur la demi-diagonale. (On a le droit d'inverser les lignes colonnes comme montrées plus haut). Comme n est compris entre 0 et 200, je souhaite avoir une complexité polynomiale.
J'ai eu vraiment beaucoup d'idées, mais elles étaient toutes en n! ou en (n/2)!.
A mon avis faudrait faire une opération sur la matrice qui pourrait me donner le résultat de cette rotation sans les tester effectivement toutes...
Si quelqu'un à une idée, ou même une piste je suis preneur.
Merci d'avance
-----