Comment puis-je résoudre ce Puzzle?

[invite61cd0120]

Bonjour à tous,

Je travaille sur un projet et je suis tombé sur ce problème:


J'ai des nombres de 1 à 36 que je veux mettre sur une matrice 6 * 6, comment calculer le nombre de possibilités existantes, et lister toutes les solutions possibles, aucun nombre ne doit être répété sur la matrice.


Merci beaucoup.
-----

[invitef29758b5]

Salut

lister toutes les solutions possibles

Lister 36! matrice 6x6 , plusieurs générations ne suffiront pas .

[invite61cd0120]

Merci pour votre reponse,

je veux juste savoir comment les parcourir via un algorithme.

Merci infiniment

[Deedee81]

Salut,

Puisque c'est juste parcourir toutes les permutations, tu peux utiliser : https://fr.wikipedia.org/wiki/Algorithme_de_Heap
(avec quelques adaptations mineurs pour "afficher" les résultats sous forme de matrice)

[A voir en vidéo sur Futura]

[Médiat]

Salut

A raison de 1000 matrices par page (ce qui est optimiste) il faut prévoir plus de feuilles de papiers

Et un algorithme pouvant traiter 100 000 000 000 de matrices par seconde prendra plus de 117 958 310 118 563 298 283 865 années

[Deedee81]

C'est clair que si elle veut parcourir toutes les permutations du début à la fin, il lui faudrait "un certain temps" (comme le fût du canon ).

Par contre si elle veut juste parcourir le début jusqu'à ce qu'elle en ait mare ou qu'il y ait une pane de courant, où si elle veut une approche purement théorique. Why not.
Mais pour une approche pratique.... là évidemment on ne peut que parcourir une partie et il convient de dire si Heap convient ou s'il y a divers critères permettant de juger de la pertinence de l'échantillon. Les méthodes de type Monte Carlo ne se font pas n'importe comment. Mais là seule Christine pourra répondre, ça dépend totalement du projet en question dont on ne sait rien.

[invite9dc7b526]

je me demande comment on pourrait aborder des questions comme: quelle est la proportion de ces 36! matrices qui sont inversibles? ou bien : quel est le déterminant moyen de ces matrices? ou encore: quelle proportion ont un déterminant négatif? On peut évidemment estimer ces quantités par sondage aléatoire, mais est-ce qu'on pourrait calculer les valeurs théoriques, sans lister les 36! matrices?

[Paraboloide_Hyperbolique]

Bonjour,

je me demande comment on pourrait aborder des questions comme: quelle est la proportion de ces 36! matrices qui sont inversibles? ou bien : quel est le déterminant moyen de ces matrices? ou encore: quelle proportion ont un déterminant négatif? On peut évidemment estimer ces quantités par sondage aléatoire, mais est-ce qu'on pourrait calculer les valeurs théoriques, sans lister les 36! matrices?

Cela devrait pouvoir se calculer théoriquement (au moins en partie) en se servant d'un peu de combinatoire et des propriétés du déterminant. Par exemple, le déterminant est nul si une ligne/colonne de la matrice est entièrement nulle ou si deux lignes/colonnes sont combinaison linéaire d'une troisième. Reste à déterminer combien il y a de telles matrices 6x6.

[invite9dc7b526]

des matrices 6x6 contenant les entiers de 1 à 36 il n'y en a pas beaucoup qui ont une colonne nulle.

[Médiat]

En tout cas, chaque pattern correspond à (6!)² matrices en permutant lignes et colonnes

[invitef29758b5]

si deux lignes/colonnes sont combinaison linéaire d'une troisième.

Si une ligne/colonne est combinaison linéaire d' une des deux autres .
C' est le cas d' une ligne/colonne nulle

[Médiat]

En tout cas, chaque pattern correspond à (6!)² matrices en permutant lignes et colonnes

Je voulais dire en permutant les lignes entre elles et/ou les colonnes entre elles.


Si compter les matrices telles qu'une colonne soit multiple d'une autre est assez simple (et encore) mais compter les matrices où 5 colonnes sont nécessaire pour exprimer la 6ième me paraît très compliqué (ou je rate quelque chose).

[invite9dc7b526]

tiens, je me suis amusé à tirer au hasard cent mille matrices 6x6 avec les nombres entiers de 1 à 36 et j'ai tracé l'histogramme de leurs déterminants. Comme on a une belle courbe en cloche centrée sur zéro, on pourrait penser que la proportion de matrices non inversibles n'est pas négligeable, mais en fait aucune des cent mille matrices n'a un déterminant nul. Le déterminant le plus petit en valeur absolue est 1021. On peut pourtant facilement fabriquer des matrices avec deux colonnes proportionnelles et donc non inversibles. Mais elles sont très peu nombreuses comparativement à 36!.