Discussion :

[mougel]

Bonjour,

Je recherche toutes les matrices 9x9 comportant 5 fois le nombre 1 dans chaque ligne et dans chaque colonne (tous les autres éléments de la matrice sont nuls).

Je ne sais programmer qu'en VBA et je ne m'en sors pas. Non seulement mon algorithme semblent durer indéfiniment, mais de plus je ne suis pas sûr qu'il soit correct.

Ce problème vous semble-t-il facile?
Quelqu'un pourrait-il m'indiquer des pistes?

Merci par avance pour vos réponses...

Edit: le nb 1 doit apparaître 5 fois exactement dans chaque ligne et chaque colonne

[PRomu@ld]

toutes les matrices 9x9 comportant 5 fois le nombre 1 dans chaque ligne et dans chaque colonne

Il te faut 5 fois et exactement 5 fois ou 5 fois au moins ?

Ce problème vous semble-t-il facile?

En fait, il s'agit d'un problème de génération de permutations. Imagine ta matrice comme un tableau de 9 cases :

| X | X | X | X | X | X | X | X | X |

Le but du jeu, c'est de trouver toutes les permutations qui ont 5 fois le 1 dedans. Disons que la première est celle ci :

| 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 |

La suivante sera éventuellement celle ci :

| 0 | 0 | 0 | 1 | 0 | 1 | 1 | 1 | 1 |

Et ainsi de suite ... . Le problème de la génération de combinaisons n'est absolument pas nouveau (il est même à la mode ces derniers temps ). Tu trouveras tout ce dont tu as besoin en effectuant une recherche sur les derniers posts de ce forum.

[Trap D]

Trsè simple à faire en Prolog : inspire toi de ce qui est fait ici

[Zavonen]

Une approche analytique.
Les matrices du type cherché sont invariantes par toute permutation des lignes.
Même remarque pour les colonnes.
On peut donc supposer que:
M(1,9)=M(2,9)=...=M(5,9)=1
avec M(6,9)=....M(9,9)=0
et aussi:
M(9,1)=M(9,2)=...=M(9,5)=1
avec M(9,6)=...=M(9,9)=0
le nombre total trouvé pour cette configuration sera à multiplier par
C5,9 ^2 soit 15876
Partageons maintenant la matrice en 4 blocs:
le bloc B1 5 premières lignes, 5 premières colonnes, 25 coefficients
le bloc B2 4 dernières lignes 4 drnières colonnes, 16 coefficients
les deux rectangles restants
B3,B4
Appelons n1,n2,n3,n4 le nombre de 1 dans B1,B2,B3,B4
on a quelques relations évidentes:
n1+n2=25
n1+n3=25
n2+n3=20
n2+n4=20
Mais on sait que dans le bloc B2 il ne peut y avoir de 1 ni dans la dernière ligne, ni dans la dernière colonne. Le nombre maximum de 1 est donc 9 (pour la configuration choisie).
Tous ces 1 se trouvent sur les 3 premières lignes et les trois premières colonnes de B2.
Le nombre total des possibilités est donc : 2^9=512 pour la répartition des 1 dans B2.
Cela dit il y a une symétrie dans ce problème par rapport à la première diagonale de la matrice.
Ce qui signifie que sur les 512 possibilités pour le bloc B2 on ne peut en retenir que 256. (Il faudra ensuite multiplier les possibilités par 2)
n2 étant connu on a immédiatemment n3,n4 et n1 en fonction de n2
Je propose donc la méthode suivante:
Faire une étude exhaustive des 256 possibilités pour B2
Pour chaque candidat compléter B3 de toutes les manières possibles
Il est inutile de faire la même chose pour B4 (symétrie diagonale)
reprendre alors les triplets trouvés et pour chacun compléter B1 de toutes les façons possibles.
Il me semble qu'on doit ainsi éviter une 'explosion', mais ça reste à vérifier.

[Zavonen]

Toutes vérifications faites, cela ne donne pas grand chose.
Je n'ai guère avancé dans la résolution de ce problème, long à coup sûr, mais pas forcément simple.
Juste quelques petits résultats, si cela peut éclairer.
pour n=1 (somme des lignes et des colonnes =1). Il y a 9! solutions, obtenues en permutant de toutes les façons possibles, les lignes (ou les colonnes) de la matrice unité.
On peut remplacer 5 par 4 en inversant le rôle des 0 et des 1.
Je ne vois rien d'autre pour le moment.

[pseudocode]

Je n'ai guère avancé dans la résolution de ce problème, long à coup sûr, mais pas forcément simple.

Comme l'a dit PRomu@ld, c'est une enumeration des permutations (avec contrainte).

il y a 126 configurations possibles pour une ligne. Donc 126^9 configurations possibles pour la matrice, sans tenir compte de la contrainte.

Ca nous laisse quand meme plusieurs millions de solutions pour le probleme avec contrainte. Est-ce bien raisonnable de toutes les enumerer ?

[Rakken]

Et l'algorithme naif ?
Pour avoir toutes les solutions d'une ligne, on liste les cas comme quand on compte en binaire, ca donne
000000000
000000001
000000010
000000011
000000100
000000101
...
111111111
Soit, a vue de nez 512 solutions. Parmis celle là, on récupere seulement les solutions qui ont leur somme à 5, une boucle et une addition et le tour est joué.
On va obtenir un tableau avec les combinaisons valides (on va appeler c1 la premiere combinaison valide (000011111) c2 la suivante (000101111), etc)
c1-c1-c1-c1-c1-c1-c1-c1-c1 donne donc avec cette notation :
000011111
000011111
000011111
000011111
000011111
000011111
000011111
000011111
000011111
Après, on prend la premiere ligne et on lui mets en seconde ligne toutes les lignes valide. Puis, pour chaque couple ainsi obtenu, on combine encore avec toutes les lignes valide, etc jusqu'a 9. (Et 9 foreach imbriqué, ca fait mal a la machine ^^)
Les matrices vont ressembler à c1-c1-c1-c1-c1-c1-c1-c1-c1, c1-c1-c1-c1-c1-c1-c1-c1-c2, c1-c1-c1-c1-c1-c1-c1-c1-cn ... cn-cn-cn-cn-cn-cn-cn-cn-cn
La déjà, on passe a un nombre de solution beaucoup plus (trop) grand, mais on est pas obligé d'explorer tous les cas.
c1-c1-c1-c1-c1-...) (avec le reste de 0) est faux parce que pour les colones, on a déjà trop de 0 et on ne pourra plus obtenir assez de 1 dans la premiere colone. Donc toute la liste des solutions commencant par c1-c1-c1-c1-c1 est fausse.
En fait, on peut du coup assez facilement construire un arbre de solutions, en éliminant les branches au fur et a mesure de la construction.
Ca fait nbdereponsevalidepouruneligne^9 solutions a explorer avec des découpes d'arbres sauvages qui doivent réduire pas mal l'exploration proprement dite.

Alors je ne garanti pas que ce soit l'algo le plus rapide pour trouver toutes les solutions mais je crois que ca peut le faire quand même.

[mougel]

Alors je ne garanti pas que ce soit l'algo le plus rapide pour trouver toutes les solutions mais je crois que ca peut le faire quand même.

C'est bien ce que je cherche: un algorithme suffisamment bourrin pour être facilement sûr qu'il ne comporte pas d'erreur.

Malheureusement, il me semble qu'un tel algo prend des siècles à s'exécuter.

Alors il faut effectivement faire des découpes de branches inutiles (correspondant à des matrices non valides, ou permutées de matrices déjà vues)
Mais la découpe doit être méthodique et intelligente: Voilà plusieurs fois que je détecte dans ma recherche une grosse erreur qui m'a fait découper par erreur telle ou telle branche, ou laisser telle ou telle branche inutile.

Ce que je cherche ici, c'est l'idée géniale qui apporterait méthode, clarté et efficacité. On a bien le droit de rêver, non?

[Nemerle]

Et l'algorithme naif ?
Soit, a vue de nez 512 solutions. Parmis celle là, on récupere seulement les solutions qui ont leur somme à 5, une boucle et une addition et le tour est joué.

....

Y en a 126, et donc ton algo "naif" doit parser 126^9 cas, soit ~ 10^19= 10 000 000 000 000 000 000 cas.

T'as un réseau de Cray?