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