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 ?

[fremen167]

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 ?

On doit pouvoir pousser l'analyse du problème un peu plus loin.

Si on part de la solution suivante :
111110000
111100001
111000011
110000111
100001111
000011110
000111100
001111000
011110000

et qu'on utilise le fait que toutes les permutations d'une solution sont aussi solution, on peut générer un ensemble de solutions simplement :

Si V et H sont respectivement la permutation verticale et horizontale appliquées, alors V°H est la fonction qui permet de déduire 1 solution de la solution initiale.

On peut définir chaque solution de la manière suivante :
si on numérote de 1 à 9 les lignes de la solution prototype (qui sont les mêmes que les colonnes d'ailleurs), 1 permutation peut être représentée par 1nombre composé des 9 chiffres (la solution initiale correspond à la permutation (1,2,3,4,5,6,7,8,9)). Il y a donc 9 ! permutations possibles, et elles sont toutes diffférentes car les 9 lignes sont différentes.
Il y a donc 9 ! ^ 2 solutions, générées à partir des différents arrangements.

Ce qui reste à voir, c'est s'il y a d'autres classes de solutions (d'autres solutions prototype). Si quelqu'un peut prendre le relai, ce serait sympa

[mougel]

Merci à tous pour vos lumières...

Effectivement, on peut simplifier le pb en supposant:
- Que chaque ligne de la matrice a ses éléments classés par ordre croissant
- Que les lignes de la matrice sont classées par ordre lexicographique.
- Que l'on ne considère pas comme distinctes deux matrices "isomorphes", càd égales moyennant une permutation des lignes suivie d'une permutation des colonnes

C'est un pb de graphes, dont voici une présentation imagée:

"Un professeur de sciences naturelles enseigne à une classe de 45 élèves, composée de 9 familles de 5 élèves.
Il souhaite les envoyer à la découverte de la flore dans le parc naturel proche de l'école.

Pour favoriser le calme, il leur propose de constituer des petits groupes de 5, qui évolueront chacun de leur côté.

De plus, afin de susciter les rencontres entre élèves, il demande que chaque élève ne se mette pas dans le même groupe qu'un membre de sa famille : chaque groupe doit donc être composé d'élèves appartenant à des familles différentes.

Combien de regroupements différents la classe peut-elle constituer selon ces critères?"

Merci pour votre aide.

J'ai tellement cherché ce pb sans succès que je me replie aujourd'hui sur la recherche d'une méthode d'inventaire bourrin de toutes les solutions, associée à une détection - tout aussi bourrine- d'élimination des solutions équivalentes entre elles.
Mais toute proposition moins désespérée est la bienvenue

[fremen167]

Merci à tous pour vos lumières...

Effectivement, on peut simplifier le pb en supposant:
- Que chaque ligne de la matrice a ses éléments classés par ordre croissant
- Que les lignes de la matrice sont classées par ordre lexicographique.
- Que l'on ne considère pas comme distinctes deux matrices "isomorphes", càd égales moyennant une permutation des lignes suivie d'une permutation des colonnes

Il me semble que seul le 2ème critère doit être retenu (lignes triées par ordre lexicographiques).

Tu ne peux pas imposer l'odre sur les éléments de chaque ligne, car pour ordonner une ligne, il faut permuter des colonnes entières, donc modifier l'ordre des éléments des autres lignes.

La solution que j'ai utilisée comme exemple (avec une petite erreur d'ailleurs) serait, ainsi triée :
000011111
000111110
001111100
011111000
100001111
110000111
111000011
111100001
111110000

Si on génère les 126 lignes / colonnes possibles (qu'on peut appeler LC(1).. LC(126)) selon cet ordre, on a beaucoup (9!) moins de possibilités à explorer puisqu'on impose que L1<L2, etc.

Donc si L1 = LC(I1), alors tous les Ln sont LC(In) avec In > I1, et plus généralement i > j ==> Ii > Ij.

Je remarque que dans "ma" solution, on a à la fois le min et le max des LC...

[Zavonen]

Le nombre cherché est: Bv[9,4,9,4] = 315031400802720
lequel est égal à Bv[9,5,9,5]
J'ai trouvé cela en suivant le lien:
http://cs.anu.edu.au/~bdm/data/semiregular.html
Pour le moment rien de plus.
Juste un moyen de vérifier pour qui aurait une solution théorique.
Pour le moment je n'arrive pas à trouver l'article fournissant la base théorique de ces calculs.

[Zavonen]

La piste australienne:
The problem of obtaining an asymptotic formula for the number of 0-1 matrices with specified row and column sums has been well studied. Counting these matrices is equivalent to counting bipartite graphs with specified degrees. The total number of entries in the matrix equal to 1 (equivalently, edges in the graph) is the parameter which tends to infinity. In the sparse case, when all row and column sums are small, the combinatorial method of switchings can be applied. However, in the dense case completely different methods are used: the problem is reduced to the evaluation of a multidimensional complex integral. Intriguingly, in all known cases the answer can be written using the same formula involving binomial coefficients.

This is joint work with Rod Canfield, Brendan McKay and Xiaoji Wang.
Bien que ces textes soient référencés souvent, IMPOSSIBLE (pour le moment) d'accéder au papier original.

[pseudocode]

Bien que ces textes soient référencés souvent, IMPOSSIBLE (pour le moment) d'accéder au papier original.

http://web.maths.unsw.edu.au/~csg/pa...ular-final.pdf

[Zavonen]

Beaucoup trop fort pour ce que nous voulons:

Let s = (s1; : : : ; sm) and t = (t1; : : : ; tn) be vectors of non-negative integer-
valued functions with equal sum S =
Pm
i=1 si =
Pn
j=1 tj . Let N(s; t) be the number
of m  n matrices with entries from f0; 1g such that the ith row has row sum si
and the jth column has column sum tj.

Nous nous intéressons seulement au cas où m=n et
s1=.....=sm=k
t1=...=tn=h
et h=k
précisemment m=n=9
k=h=5
L'article ne se lit pas vraiment comme un roman de gare ...
Il doit y avoir qqch de plus simple pour notre cas.

[Nemerle]

juste une idée qui me revient: avez-vous essayé de regarder le problème coté matrices définie positive & théorie spectrale? Je crois me souvenir que les matrices positives à somme de lignes constante C ont des propriétés, par exemple elles on toutes pour rayon spectral la valeur C...

P'tèt qu'elles on toute une certaine forme de décomposition spectrale? Enfin, tout cela est loin... mais y a probablement une étude sur "les matrices 9x9 booléennes M dont la somme des termes de chaque lignes de M et de sa transposée t(M) est toujours constant".

[mougel]

Il me semble que seul le 2ème critère doit être retenu (lignes triées par ordre lexicographiques).

Tu ne peux pas imposer l'odre sur les éléments de chaque ligne, car pour ordonner une ligne, il faut permuter des colonnes entières, donc modifier l'ordre des éléments des autres lignes.

Effectivement, ce critère est de trop.

Mais une fois qu'on a un ensemble de matrices conformes (matrices 9x9 dont les lignes et les colonnes comportent 5 fois le nombre 1, tout le reste nul) comment détecter les matrices équivalentes (à une PC°Pl près)?
Mon approche actuelle est de ne considérer que les matrices conformes dont les lignes sont classées par ordre lexicographique, et de relever ces matrices dans l'ordre lexicographique (en effet, les matrices elles-mêmes peuvent être classées par ordre lexicographique), et de rejeter toute matrice dont l'image par une Pc (permutation de colonnes) donne une matrice de rang lexicographique inférieur.
Cette approche ne rejette que des matrices équivalentes à des matrices déjà retenues, mais ne rejette pas TOUTES les matrices équivalentes.

Mais je vois que certaines approches proposées ici doivent être approfondies.

Je suis impressionné par le niveau de ce forum...

Merci à vous

[mougel]

[QUOTE=Nemerle;2640171]juste une idée qui me revient: avez-vous essayé de regarder le problème coté matrices définie positive & théorie spectrale? Je crois me souvenir que les matrices positives à somme de lignes constante C ont des propriétés, par exemple elles on toutes pour rayon spectral la valeur C...
QUOTE]

Je ne connais pas bien cette théorie, mais je sais qu'il existe des matrices booléennes symétriques qui ont exactement les mêmes valeurs propres (et le même ordre de multiplicité pour chaque valeur propre), mais qui pourtant ne sont pas isomorphes (i.e. égales à Pl°Pc près). C'est un certain CHANG qui a trouvé un exemple de telles matrices, connues sous le nom "Graphes de Chang"

[Nemerle]

c'est un système de générateurs que tu cherches, mais ce que tu dis ne présage rien de bon: soit Chang a exhibé un exemple, soit il donne des générateurs pour un certain type de problème, et là c'est mieux...

[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.

[pseudocode]

"Un professeur de sciences naturelles enseigne à une classe de 45 élèves, composée de 9 familles de 5 élèves.
Il souhaite les envoyer à la découverte de la flore dans le parc naturel proche de l'école.

Pour favoriser le calme, il leur propose de constituer des petits groupes de 5, qui évolueront chacun de leur côté.

De plus, afin de susciter les rencontres entre élèves, il demande que chaque élève ne se mette pas dans le même groupe qu'un membre de sa famille : chaque groupe doit donc être composé d'élèves appartenant à des familles différentes.

Combien de regroupements différents la classe peut-elle constituer selon ces critères?"

C'est moi ou je trouve que le probleme d'origine est nettement plus simple que celui du PO...

[Nemerle]

http://web.maths.unsw.edu.au/~csg/pa...ular-final.pdf

Une variante: http://www.emis.de/journals/EJC/Volu...F/v12i1r29.pdf