Petit problème agaçant de combinatoire.

[Mario2015]

Je vous ai done le principe de ma methode.
Si 22 ne marche pas je rajoute une ligne et ainsi de suite jusqu`a trouver le minimum couvrant tous les triplets.

[Mario2015]

Salut,
tu prends les entiers compris entre 1 et 12.
Il existe 792 5-combinaisons.
IL existe 220 3-combinaisons.

Quel est le plus petit nombre de 5-combinaisons à choisir permettant de retrouver toutes les 220 3-combinaisons ?

Je pense avoir trouve un principe de solution.
Pour n=12 il y a 792 quintuplets
On a besoin de 22 quintuplets pour couvrir les 220 triplets.
L`idee est la suivante et elle peut etre programmee.
Si on partitionne au hasard l`ensemble des 792 quintuplets en sous-ensembles de 22 quintuplets. Il y en aurait 36 (36*22=792).
Chaque sous-ensemble de 22 quintuplets couvrirait un certain de nombre de triplets (certains seront absents d`autres seront dupliques). D`ou l`idee de faire des substitutions de quintuplets d`un sous-ensemble a un autre de telle sorte que les triplets soient uniformement couverts. L`ideal est d`aboutir a une repartition uniforme : chaque sous-ensemble de 22 couvrirait tous les 220 triplets. L`optimum serait une distribution avec le plus faible ecart-type. On aurait ainsi parmi ces 36 sous-ensemble, un sous-ensemble de 22 qui couvre le maximum de triplets comme point de depart.
Cela dit il y a un certain nombre de problemes a resoudre pour eviter les cycles lors des substitutions.

[Mario2015]

Conclusion : cela n`interesse pas grand monde les problemes difficiles a ce que je vois. Pas meme Cauchy2010 !!!!!

[nodjim]

"Cela dit il y a un certain nombre de problemes a resoudre pour eviter les cycles lors des substitutions".

C'est surtout ta dernière phrase qui interpelle, je crois.

[Mario2015]

"Cela dit il y a un certain nombre de problemes a resoudre pour eviter les cycles lors des substitutions".

C'est surtout ta dernière phrase qui interpelle, je crois.

En disant cela, je pose en fait la question : comment faire une substitution optimale?
On a 36 sous-ensemble de 22 quintuplets.
A chacun de ces 36 sous-ensembles est associe un taux de couverture des 220 triplets.
Certains auront un taux de couverture bas (le nombre de triplets non couverts est eleve) d`autres un peu plus eleves. La substitution vise a equilibrer au mieux les taux de couverture. Si la solution parfaite existe on aurait un taux de couverture de 100% pour chacun des sous-ensembles. Si elle n`existe pas on aurait au mieux un taux de couvertrre maximale d`un sous-ensemble de 22 quintuplets. Partant de la, on peut rajouter des quintuplets de maniere a couvrir le reste. La encore, c`est une histoire de choix optimal.

[Mario2015]

Je vais tester cela sur Excel (un tableau de 792 lignes et 220 colonnes).
C`est lourd et cela prend du temps mais c`est faisable.

[Mario2015]

Que pensez-vous de la solution exposee ci-dessus?

[Cauchy2010]

Conclusion : cela n`interesse pas grand monde les problemes difficiles a ce que je vois. Pas meme Cauchy2010 !!!!!

C'est un peu idiot ce que tu dis, puisque c'est moi qui ai posé le pb et admis que je cassais les dents dessus depuis un certain temps ! :zen:

[Cauchy2010]

Que pensez-vous de la solution exposee ci-dessus?

elle est fausse, mon grand ! tu vas t'en apercevoir tout seul ! Je peux te donner une règle de fabrication informatique, mais je n'arrive pas au 29 5-combinaisons trouvés et figurant sur la toile. :++:

[Mario2015]

elle est fausse, mon grand ! tu vas t'en apercevoir tout seul ! Je peux te donner une règle de fabrication informatique, mais je n'arrive pas au 29 5-combinaisons trouvés et figurant sur la toile. :++:

Dire que c`est faux sans expliquer pourquoi me semble errone comme demarche.
Je vais tester cela sur Excel (pas tout de suite parce que je suis sur autre chose).

[Mario2015]

Comme tu cherchais une liste des methodes utilisees, vas la et lis vers le mileu de la page "methods used in current tables ":

http://www.ccrwest.org/cover/top.html

[Cauchy2010]

Comme tu cherchais une liste des methodes utilisees, vas la et lis vers le mileu de la page "methods used in current tables ":

http://www.ccrwest.org/cover/top.html

Merci bien. Toutefois, la liste des méthodes sans explication de la méthode me paraît assez peu intéressant. Qu'en penses tu ?

[Mario2015]

Merci bien. Toutefois, la liste des méthodes sans explication de la méthode me paraît assez peu intéressant. Qu'en penses tu ?

Lle site ne fait que reproduire ce que les contributeurs envoient. Il verifie si les combinaisons couvrent ou non les combinaisons requises. Les contributeurs ne sont pas obliges de fournir leurs methodes.
Je leur ai deja envoye des combinaisons. Ils repondent rapidement en general.
En plus, ce domaine est ouvert et les methodes sont nombreuses. Il y en a 6 ou 7 qui concentrent le gros des contributions.

[Mario2015]

Tu peux leur envoyer une contribution avec methode Mario ils ecriront methode Mario.
Ils verifient tes combs si elles sont bonnes ils te publie.
Le site neerlandais que je n`arrive pas a retrouver publie juste les combinaisons et le nonm de leur auteur avec la date de creation.

[Mario2015]

elle est fausse, mon grand ! tu vas t'en apercevoir tout seul ! Je peux te donner une règle de fabrication informatique, mais je n'arrive pas au 29 5-combinaisons trouvés et figurant sur la toile. :++:

Si ma methode est fausse il faudrait dire pourquoi.
J`attends toujours ton explication.

[Mario2015]

Je viens de retrouver dans mes archives les documents sur les methodes de couverture (covering systems). Je suis tres brouillon, je cherche, je telecharge et je classe cela quelque part en me basant sur ma memoire. La, je dois partir. A demain

[Mario2015]

A @Cauchy2010

Dire qu`une methode est fausse sans dire pourquoi me sidere tout simplement.
Libre a toi de repondre ou de ne pas repondre.
Moi je decide tout simplement de ne plus intervenir.
Entre nous, je commence a avoir ras-le-cul des forums, de tous les forums.
Une perte de temps le plus souvent.
Cela dit, merci quand meme.
Adios y buena suerte!

[Cauchy2010]

Ne t'énerve pas, on ne passe pas tout notre temps devant notre écran, il y a autres choses à faire dans la vie quotidienne.
Ta méthode n'est pas "fausse", elle est utopique. Mais tu réfléchis bien, c'est déjà bien.
So long !

[nodjim]

Ben oui quoi Mario travaille sur ce problème depuis des années, et on l'envoie bouler d'un claquement de doigt, ce n'est pas sympa.
Sa méthode proposée est très séduisante, car elle implique une convergence vers la solution optimale: d'une situation de départ déséquilibrée, on fait des échanges pour rééquilibrer les triplets dans les 36 groupes de 22 quintuplets. Elle mérite d'être testée. Mais elle est longue et le programme pour la faire tourner n'est pas forcément simple à élaborer.

[Cauchy2010]

Le problème est que c'est une méthode "manuelle", sans logique sous-jacente et donc, non généralisable.
J'avais posé la question il y a quelque années à un brillant ENS Cachan, agrégé, informaticien en activité dans le privé, qui avait conclu que c'était un sujet dont la principale complication était de s'assurer de la minimalité de la solution.
Un autre brillant informaticien (en retraite) avait conçu une solution codée sous python que je peux poster, il pensait avoir trouvé le minimum minimorum (32 quintuplets) jusqu'au jour où il est "tombé" sur la solution avec 29 seulement publiée sur la toile. Il n'a pas encore compris comment le gars avait fait.
A l'analyse de son pgm, je m'étais aperçu que la solution dépendait du choix de la première grille.
D'où ma quête.
Et merci à Mario pour ses réponses.
Ma vraie question n'est pas tant de savoir comment faire pour sélectionner les bonnes grilles que de trouver la bonne technique pour dénombrer le nombre minimum de grilles satisfaisant la contrainte.
L'esprit reste encore supérieur à l'informatique.