Comment construire un "recouvrement" minimal de combinaisons ?

[choom]

Soit les 42 premiers nombres entiers, de 1 à 42.
Soit EC3-42 l'ensemble de toutes les combinaisons simples sans répétitions de 3 de ces 42 nombres.
EC3-42 contient 42 x 41 x 40 / 3 x 2 éléments.

Comment obtenir "S", l'un des PLUS PETITS sous-ensembles possibles de EC6-42 ( soit des combinaisons simples de 6 de ces 42 nombres) ayant la propriété que TOUS les éléments de EC3-42 se trouvent AU MOINS
être l'une des 20 combinaisons à 3 chiffres que l'on peut former à partir d'un des élément de "S".
Et quel est le cardinal de "S" pour que "S" soit le plus petit ?

Pour les joueurs cela revient à déterminer de quelle manière dépenser le moins d'argent possible à un jeu de LOTO où l'on pourrait cocher 6 cases sur un bulletin de 42, tout en étant certain d'au moins gagner 20 fois le petit lot de consolation attribué aux bulletins ayant coché 3 des 6 nombres gagnant.

Note :les nombres 42, 6 et 3 ne sont là que pour concrétiser la question.
Ce qui m'intéresse d'apprendre est le raisonnement à suivre dans un cas général de N > M > P
Cela fait longtemps que je m'y casse les dents.

Bon amusement aux théoriciens de l'analyse combinatoire....
-----

[choom]

Mille excuses : la politesse n'étant pas une option, j'ai pourtant manqué à l'élémentaire élégance de commencer ma question par vous souhaiter BONJOUR : je ne suis pas un habitué des forums....

[Médiat]

Bonjour,

La question que vous posez est très difficile (à ma connaissance), il suffit, pour s'en convaincre de vérifier pour les faibles valeurs N,
Pour N = 6, M = 6, P = 3, on trouve qu'il faut 1 sous-ensembles
Pour N = 7, M = 6, P = 3, on trouve qu'il faut 4 sous-ensembles
Pour N = 8, M = 6, P = 3, on trouve qu'il faut 4 sous-ensembles
...

[choom]

En effet, Mediat : en fait elle me trotte en tête depuis des années, et je n'ai pas encore trouvé la moindre piste mathématique pour aborder un énoncé qui, vu du point de vue d'un joueur, est pourtant pertinent :
il y a 35 ans, du temps où le loto en Belgique n'avait que 40 cases, j'ai généré par programmation une solution pour S donc avec N=40 M=6 P=3 mais sans aucune certitude théorique que S était minimal.
Pour la petite histoire nous avons joué à 3 l'ensemble des combinaisons.. et avons récupéré le minimum prévu plus par chance quelques groupes de 4 : en tout presque la moitié de notre mise. Il vaut donc mieux ne pas compter là dessus pour devenir riche.
Mais le problème mathématique, lui, me titille toujours autant....

[A voir en vidéo sur Futura]

[Toufou]

Bonsoir,

Punaise ! Effectivement, c'est "chaud" comme problème !!

Déjà, en codant un truc vite fait, si je ne me suis pas vautré, il ne semble pas possible de couvrir les Ec3-42 sans répétitions dans les combinaisons au niveau des Ec6-42.
Au mieux, je "couvre" 6140 des 11480 combinaisons de Ec3-42 avec 307 combinaisons prisent dans Ec6-42.

Du coup, bein, je cherche pour les 5340 qui manquent en minimisant les répétitions...

[mike.p]

Salut,

pour les cas particuliers remarquables, vous devriez chercher "Steiner Systems" ( et ignorer Steiner Trees )

Sinon, la référence sur ce problème ouvert dans le cas général est :
Daniel M. Gordon, Oren Patashnik, Greg Kuperberg (1995) New constructions for covering designs, J. Combinatorial Designs extrait pages 269-284 sur Arxiv

[choom]

Wouaw, Mike P, merci !
Cette référence concerne en effet pile poil le problème posé.
Je m'attelle de suite à une lecture approfondie.
Christian

[Toufou]

Bonjour,

Pour l'amusement, je trouve un minimum de 819 combinaisons de EC6-42 pour couvrir EC3-42.

Il y a pas mal de triplets qui sont répétés mais l'essentiel est de couvrir tout EC3-42 et puis si on se place dans l'hypothèse d'un loto si les triplets répétés sont des triplets qui "sortent" c'est tout bénéfice !

Pour mon algo., je viens de lire l'article en référence, et en gros, j'ai fait un truc qui ressemble à ce qu'ils nomment le "greedy coverings" mais avec peut-être du plantage en supplément

[choom]

Excellent, Toufou. Je n'ai pas encore eu assez de temps libre pour faire de même, mais ton résultat est vraiment encourageant.
Ce forum est vraiment sympa ET efficace ! Je ne pensais pas avancer si vite vers la résolution.
Je reviendrai vers toi pour plus détails sur ta méthode si je n'arrive pas à faire mieux de mon côté.
( En attendant, la course à un meilleur résultat reste ouverte à tous ceux que l'analyse combinatoire amuse... )

Christian

[Toufou]

Bonjour,

En regardant dans mon fichier de sauvegarde, je me suis rendu compte que je n'avais que 800 combinaisons d'enregistrées et, effectivement, j'avais un compteur mal placé quelque part.

Du coup, un nombre tout rond de 800, j'ai comme un gros doute...

Je vais laisser la place à plus expérimenté que moi mais je serais vraiment curieux de connaître le résultat ! (*)




(*) Peut-être dans un autre topic ou sur un autre forum car c'est un peu annexe au problème mathématique en lui même.

[choom]

@toufou : 800 x 20 = 16000 pour couvrir 42 x 41 x 40 / 3 x 2 = 11480 c'est déjà performant et crédible : cela ne fait que 39,4% de triplets doublonnés par rapport à la cible. As-tu pu vérifier que la cible est bien couverte ?

[Toufou]

J'ai un vecteur de pointage des 11480 combinaisons de C3-42 que je vérifie à la fin et tout est bien couvert mais de là à affirmer que j'obtiens un S min...
Il faudrait que je test mon algo. sur un problème similaire dont la solution est connue avec certitude.

[mike.p]

Salut,

avez vous travaillé sur le cas d'un loto de 6 parmi 36 toujours à la recherche de la couverture de triplets ?
( non, je n'ai pas le résultat sous la main )

[Toufou]

Bonsoir,

Dans le cas avec 36 au lieu de 42, je trouve 505 combinaisons.

[mike.p]

Salut,

jolis 800 et 505 !

j'ai fait un nano outil pour tenir à jour les listes de combinaisons, le crible et les performances.
Il ne reste plus qu'à tracer les lignes de 6 en faisant le moins de doublons possibles.

J'aimerais partir d'un Steiner en 6 et 3 et voir comment apparaissent les difficultés, c'est à dire les doubles recouvrements, quand on augmente le nombre total de nombres. C'est facile à suivre quand on passe de 42 à 43 mais plus difficile de 36 à 42 ou 42 à 48 et pire encore 49.

[Toufou]

Bonjour,

En tombant de mon lit ce matin, j'ai eu une grosse interrogation sur l'approche "greedy coverings".
Je me demande si le résultat ne risque pas de varier selon la façon dont on parcourt les combinaisons !?

Dans mon cas, j'ai pris l'ordre lexicographique mais en générant les combinaisons dans un autre ordre j'ai comme dans l'idée que ça va se "croiser" autrement et risque de donner un autre résultat, non !?

Merci pour le casse-tête Choom !!

[mike.p]

Bonjour,

Steiner: 42,6,3
total: 11480
reste: 0
doublons : 502
grilles : 644
minimum : 574 , obtenu par itération, susceptible d'être amélioré.
Mais comme indiqué, on ne sait pas si cet arbre de chemins existe.

Malgré un gros paquet d'efforts nocturnes, je ne suis pas arrivé à faire mieux que 644 avec la méthode cyclique ( cf pdf arxiv plus haut ). Des tentatives d'amélioration n'ont rien donné, au contraire. Cependant, il reste des tas d'autres générateurs à tester.

Another well-known method that is often successful when applicable—when the size of a prospective covering is v—is
to construct a cyclic covering: Choose some k-subset as the first block, and choose the v− 1 cyclic shifts of that block
as the remaining blocks. Trying this for all possible k-sets is fairly cheap, and frequently it produces a covering. The
entries C(19,9,3) ≤ 19 and C(24,10,3) = 24 in our tables, for example, are generated by the k-sets 1 2 3 4 6 8 13 14 17
and 1 2 3 5 6 8 12 13 15 21, and are unmatched by any other method.
Incidentally, if the size of a prospective covering is a multiple of v, say 2v, the same method applies by taking the cyclic
shifts of two starting blocks; the few cases we tried for this variation produced no improvements in the tables

Avec d'autres paramètres que 6 et 3 ou 5 et 3, j'obtiens des recouvrements de qualité variable. Il faut encore tâtonner.

Pour euromillion ( 50,5,3) j'obtiens 2235 et pour ( 36,6,3 ) 478 mais 8101 pour ( 42,5,3) ... J'ai du bugguer ce matin

J'ai aussi noté , comme indiqué et expliqué dans le pdf , qu'il est possible de passer (n-1,p,q) et (n-1,p-1,q-1) pour faire un (n,q,p) de bonne qualité mais moins bonne qu'un résultat cyclique direct.

Il me semble avoir fait bien mieux il y a 20 ans avec un 386 ou un 486 et très peu de mémoire. C'était bien un (42,6,3) et suis certain qu'il y a une solution avec 314 doublons seulement.

J'ai aussi noté des similitudes avec d'autres énigmes et assimilées en cours sur FS. Quoique tous les graphes de liaisons à 3 se ressemblent ...

[mike.p]

Le minimum est calculable par itération mais bien entendu, il ne peut être inférieur à la diversité des tirages à 3 et ici les 2 coincident ( 574 ) , ce qui laisse croire à une solution possible avec 574 grilles de recouvrement ...

[Toufou]

Bonsoir,

Excellent ! Impressionnante amélioration !! Bravo !

[mike.p]

Bonjour !

c'est surtout la méthode qui est plus performante dans certains cas. Vous avez du utiliser les lexicodes , une approche plus riche et plus didactique à priori. L'ordre compte. Il faudrait lire Natalia Silberstein ...

[Toufou]

Bonsoir,

Ayant eu un peu de temps libre, j'ai refait quelques tentatives, d'abord infructueuses, en Lex, Co-Lex, random...
...et finalement en M.C.O (Minimal Change Order ou code de Gray) je suis tombé sur un minimum de 574 soit une couverture parfaite, ce que je pensais pourtant impossible l'autre jour !?

Je précise, qu'auparavant, j'ai testé mon algo sur un cas avec réponse certaine et j'ai obtenu le bon minimum

Je ne sais pas pourquoi mais le M.C.O semble fonctionner particulièrement bien pour ce genre de problème.
J'ai lu qu'il y aurait un lien avec les chemins Hamiltonien dans le domaine des graphes, mais bon, je ne serais pas contre un peu plus d'explications...

[choom]

Wouaw. Alors là chapeau. Suis intéressé !

[mike.p]

Bonjour,

Bonsoir,

Ayant eu un peu de temps libre, j'ai refait quelques tentatives, d'abord infructueuses, en Lex, Co-Lex, random...
...et finalement en M.C.O (Minimal Change Order ou code de Gray) je suis tombé sur un minimum de 574 soit une couverture parfaite, ce que je pensais pourtant impossible l'autre jour !?

Je précise, qu'auparavant, j'ai testé mon algo sur un cas avec réponse certaine et j'ai obtenu le bon minimum

Je ne sais pas pourquoi mais le M.C.O semble fonctionner particulièrement bien pour ce genre de problème.
J'ai lu qu'il y aurait un lien avec les chemins Hamiltonien dans le domaine des graphes, mais bon, je ne serais pas contre un peu plus d'explications...

Bravo ! je n'avais pas vu votre message hier soir ...
MCO je l'utilise dans une solution de jeu de dames ! il vaut mieux qu'il y ait une solution sinon ça peut ramer. Enfin, ça dépend de l'implémentation
Avez vous essayé MCO avec d'autres arbres ?

[Toufou]

Bonjour,

Bon, c'est un peu la honte, mais je me suis planté avec le M.C.O, ça ne fonctionne pas non plus.
Le bon résultat avec le problème de test était juste une coïncidence
Ce problème va me rendre chèvre !

[Toufou]

Bonjour,

Pour ceux que ce genre de problème intéresse, j'ai trouvé un site qui compile des résultats pour divers paramètres: https://www.ccrwest.org/cover.html

Si vous testez V=42, k=6, t=3, on peut voire que le meilleur résultat trouvé et publié est de 644 (Jan de Heer, Steve Muir, 2008-12-04). https://www.ccrwest.org/cover/t_page.../C_42_6_3.html

Le même résultat qu'a trouvé Mike.p !!

Pour vos recherches, il faut partir sur du «Combinatorial design»

[choom]

Un super amas de couvertures. Merci Toufou.