Répondre / Forum de mathématiques - Bibm@th.net

Forum de mathématiques - Bibm@th.net

Bienvenue dans les forums du site BibM@th, des forums où on dit Bonjour (Bonsoir), Merci, S'il vous plaît...

Vous n'êtes pas identifié(e).

Répondre

Veuillez composer votre message et l'envoyer

Les questions suivantes sont faites pour éviter le spam. Si vous voulez ne plus les avoir, inscrivez-vous!

Quel est le résultat de 37+33?

Quel est le 4 ième chiffre de 8648310?

Retour

Résumé de la discussion (messages les plus récents en premier)

totomm
27-08-2011 09:41:00

Bonjour,

@ freddy : Mon code est dans le sous-forum "Programmation"

Cordialement

totomm
24-05-2011 09:09:41

Bonjour,

petit corrigé pour le post #42 :

totomm a écrit :

Les triplets sont de 0 à 119 dans l'ordre de leur génération :

il faut lire 219 et non pas 119

Cordialement

totomm
23-05-2011 17:07:36

re,

télescopage....
merci à tous deux, une vérification ou une alerte ne sont jamais inutiles

Cordialement

totomm
23-05-2011 17:03:59

Bonjour,

Encore une fois, ne pas s'affoler, je serais ravi qu'une erreur me soit indiquée
Voici une vérification faite avant de publier mon résultat :
vérification : Les triplets sont vus 320 fois, chacun vu ce nombre de fois :
[1, 1, 1, 2, 1, 2, 1, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 3, 1, 1, 1, 1, 2, 2, 1, 2, 1, 1, 1, 2, 1, 1, 2, 2, 1, 3, 1, 3, 2, 1, 4, 1, 1, 1, 1, 2, 2, 2, 2, 1, 2, 2, 1, 1, 2, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 2, 1, 1, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 1, 1, 1, 2, 2, 1, 1, 3, 4, 1, 1, 1, 1, 3, 2, 2, 1, 3, 1, 1, 1, 1, 1, 2, 2, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 2, 1, 1, 1, 2, 2, 1, 1, 2, 1, 2, 1, 1, 2, 2, 1, 1, 1, 1, 2, 1, 2, 1, 1, 2, 2, 1, 1, 2, 3, 2, 1, 1, 2, 2, 2, 1, 1, 1, 1, 1, 1, 2, 1, 2, 2, 2, 2, 2, 2, 1, 1, 2, 1, 1, 1, 4, 1, 1, 1, 1, 1, 1, 2, 3, 1, 3, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 3, 2, 2, 1, 2, 1, 1, 2, 1, 1, 2, 1, 1, 2, 1, 2, 2, 1, 1, 2]
Les triplets sont de 0 à 119 dans l'ordre de leur génération :

J'ai donné plus haut le nombre de combinaisons retenues à chaque itération et l'ordre dans lequel elles avaient été retenues en en donnant la liste

ci-dessous les programmes écrits en Python version 3.2 pour utilisation éventuelle :
Voici la création des 5-combinaisons et des triplets:
list12_5=[]
for a in range(1,9):
    for b in range(a+1,10):
        for c in range(b+1,11):
            for d in range(c+1,12):
                for e in range(d+1,13):
                    list12_5.append([a,b,c,d,e])
list12_3=[]
for c in range(1,11):
    for d in range(c+1,12):
        for e in range(d+1,13):
            list12_3.append([c,d,e])
print("Combinaisons :")
print("12 nombres pris par 5 par 5 =",len(list12_5))
print("12 nombres pris par 3 par 3 =",len(list12_3))

Voici la vérification de la présence des triplets  dans les 32 5-combinaisons-retenues

print(combRetenus)
Tnb=[0]*len(list12_3)
nbdansTnb=0
for n in range(0,len(combRetenus)):
    cr=combRetenus[n]
    for a in range(0,3):
        for b in range(a+1,4):
            for c in range(b+1,5):
                T=[cr[a],cr[b],cr[c]]
                i=list12_3.index(T)
                Tnb[i] += 1
                nbdansTnb += 1
print()
print("vérification : Les triplets sont vus",nbdansTnb,"fois, chacun vu ce nombre de fois :")
print(Tnb)

Cordialement

yoshi
23-05-2011 16:52:02

Salut freddy,

Erreur de programmation...
Je viens de tester, totomm n'a pas fait erreur
Toutes les combinaisons de 3 symboles pris parmi 5, d'indices 0,1,2,3,4 sont au nombre de 10 :
[[0, 1, 2], [0, 1, 3], [0, 1, 4], [0, 2, 3], [0, 2, 4], [0, 3, 4], [1, 2, 3], [1, 2, 4], [1, 3, 4], [2, 3, 4]]

Il retient 32 5-combinaisons de 12 :
[[1, 2, 3, 4, 5], [1, 2, 6, 7, 8], [1, 2, 9, 10, 11], [1, 3, 6, 9, 12], [1, 4, 7, 10, 12], [2, 3, 7, 11, 12], [2, 4, 8, 9, 12], [3, 4, 6, 8, 10], [3, 5, 7, 8, 9], [4, 5, 6, 7, 11], [5, 8, 10, 11, 12], [2, 5, 6, 9, 10], [1, 3, 4, 8, 11], [1, 3, 5, 7, 10], [1, 5, 6, 8, 12], [2, 4, 6, 11, 12], [2, 4, 7, 9, 10], [6, 7, 8, 9, 11], [1, 4, 5, 9, 11], [1, 6, 7, 10, 11], [2, 3, 8, 9, 10], [2, 3, 5, 6, 11], [2, 5, 7, 8, 12], [3, 4, 5, 8, 12], [3, 9, 10, 11, 12], [1, 7, 8, 9, 10], [3, 4, 6, 7, 9], [1, 2, 6, 10, 12], [5, 6, 7, 9, 12], [1, 2, 8, 11, 12], [1, 4, 5, 6, 10], [4, 7, 8, 10, 11]]

J'ai pris chaque combinaison 1 par une, puis de chacune grâce à mes indices de combinaison, j'en ai extrait systématiquement les 10  combinaisons de 3 parmi 5 que j'ai stockées dans une autre liste.
J'ai ensuite
*  trié cette liste (c'est une "méthode de liste" built-in de Python : pas de risque d'erreur) par ordre croissant
* éliminé les doublons, triplons...
J'ai ensuite vérifié le nombre de 3-combinaisons restantes forcément différentes, réponse 220...

Donc, tout est ok !

Voilà le morceau de prog correspondant :

: Python

  1. L=[[1, 2, 3, 4, 5], [1, 2, 6, 7, 8], [1, 2, 9, 10, 11], [1, 3, 6, 9, 12],\
  2.        [1, 4, 7, 10, 12], [2, 3, 7, 11, 12], [2, 4, 8, 9, 12], [3, 4, 6, 8, 10],\
  3.        [3, 5, 7, 8, 9], [4, 5, 6, 7, 11], [5, 8, 10, 11, 12], [2, 5, 6, 9, 10],\
  4.        [1, 3, 4, 8, 11], [1, 3, 5, 7, 10], [1, 5, 6, 8, 12], [2, 4, 6, 11, 12],\
  5.        [2, 4, 7, 9, 10], [6, 7, 8, 9, 11], [1, 4, 5, 9, 11], [1, 6, 7, 10, 11],\
  6.        [2, 3, 8, 9, 10], [2, 3, 5, 6, 11], [2, 5, 7, 8, 12], [3, 4, 5, 8, 12],\
  7.        [3, 9, 10, 11, 12], [1, 7, 8, 9, 10], [3, 4, 6, 7, 9], [1, 2, 6, 10, 12],\
  8.        [5, 6, 7, 9, 12], [1, 2, 8, 11, 12], [1, 4, 5, 6, 10], [4, 7, 8, 10, 11]]
  9.  
  10. Indices=[]
  11. for i in range(0,3):
  12.     for j in range(i+1,4):
  13.         for k in range(j+1,5):
  14.             Indices.append([i,j,k])
  15.            
  16. I312=[]
  17. for i in range(32):
  18.     A=L[i]
  19.     for j in range(10):
  20.         B=Indices[j]
  21.         a,b,c=A[B[0]],A[B[1]],A[B[2]]
  22.         I312.append([a,b,c])
  23.  
  24. j=-1
  25. I312=sorted(sorted(I312))
  26. while j<len(I312)-1:
  27.     j+=1
  28.     A=I312[j]
  29.     while A in I312[j+1:]:
  30.         del I312[j+1]
  31.  
  32. print len(I312)

Par acquit de conscience après, j'ai demandé l'affichage de cette fameuse liste I312 de 220 combinaisons et j'ai vérifié une par une toutes les combinaisons : elles sont bien conformes à ce que j'attendais.

@+

freddy
23-05-2011 15:23:09

Salut,

sauf erreur de pgm de ma part, les 32 5-combinaisons proposées ne permettent de générer que 107 3- combinaisons parmi les 220 à trouver.

il doit y avoir un nouille dans le potage, mais je ne sais pas lequel et laquelle.

bis bald !

totomm
21-05-2011 15:49:16

re,

Ne vous emballez pas car je n'ai jamais refusé de donner une explication, même très longue.
Il se peut que j'aie corrigé certaines erreurs et que cela ne plaise pas. Quand j'en ai fait, il me semble que je me suis efforcé de les corriger honnêtement.
Excusez moi de dire qu'il m'a été demandé de publier mes programmes : je l'ai fait et n'ai pas eu de confirmation en retour qu'ils donnaient les résultats annoncés.
Je sais reconnaître le dévouement de certains à bien poser les raisonnements, mais aussi reconnaitre la désinvolture de certains autres.

Les problèmes posés sur ces forum sont de bon niveau, donc intéressants, et je n'ai comme prétention que de vouloir raisonner juste, et pas forcément en expliquant mieux.

Cordialement

yoshi
21-05-2011 15:02:10

RE,

Malgré toute la bonne foi que je vous concède, je suis un peu échaudé par l'accueil que reçoivent les explications détaillées données après demandes, et les promesses de vérifier les résultats demandés et publiés.
et sans même le "merci" qui semblait de mise sur ce forum.

Alors puisque tu le prends comme ça, cher ami, restons-en là : j'aurais dû éviter d'intervenir, ainsi je n'aurais pas eu à dire que je ne te trouvais pas clair, c'eut été mieux pour l'ego de chacun...
A l'avenir, je m'abstiens de tout commentaire, promis !

Vois-tu, c'est que j'avais dit : savoir pour soi, c'est bien ! Savoir pour expliquer aux autres de façon qu'ils comprennent, c'est entrer dans une autre dimension...
Je me suis montré courtois, modéré, mesuré plus exactement, dans mes interventions : mais te voir sortir la même complainte qu'avec freddy, je trouve ça un peu fort.

Sujet clos. Je ne le ferme pas pour que notre ami, s'il revient puisse te dire aussi :

MERCI.
(Là aussi, c'est un peu fort de café)

totomm
21-05-2011 14:09:42

re,

Nombre de 5-combinaisons retenues = 32
qui contiennent au moins une fois tout triplet de 3 nombres parmi les 12 :
[[1, 2, 3, 4, 5], [1, 2, 6, 7, 8], [1, 2, 9, 10, 11], [1, 3, 6, 9, 12], [1, 4, 7, 10, 12], [2, 3, 7, 11, 12], [2, 4, 8, 9, 12], [3, 4, 6, 8, 10], [3, 5, 7, 8, 9], [4, 5, 6, 7, 11], [5, 8, 10, 11, 12], [2, 5, 6, 9, 10], [1, 3, 4, 8, 11], [1, 3, 5, 7, 10], [1, 5, 6, 8, 12], [2, 4, 6, 11, 12], [2, 4, 7, 9, 10], [6, 7, 8, 9, 11], [1, 4, 5, 9, 11], [1, 6, 7, 10, 11], [2, 3, 8, 9, 10], [2, 3, 5, 6, 11], [2, 5, 7, 8, 12], [3, 4, 5, 8, 12], [3, 9, 10, 11, 12], [1, 7, 8, 9, 10], [3, 4, 6, 7, 9], [1, 2, 6, 10, 12], [5, 6, 7, 9, 12], [1, 2, 8, 11, 12], [1, 4, 5, 6, 10], [4, 7, 8, 10, 11]]

Cordialement

totomm
21-05-2011 14:04:29

re,

Malgré toute la bonne foi que je vous concède, je suis un peu échaudé par l'accueil que reçoivent les explications détaillées données après demandes, et les promesses de vérifier les résultats demandés et publiés.
et sans même le "merci" qui semblait de mise sur ce forum. Néammoins :

Faire une première itération dans les 792 5-combinaisons en ne retenant que celles qui, parmi les sous-ensembles de 10 triplets que chacune contient, fournissent des sous-ensembles disjoints. Donc 110 triplets différents contenus dans 11 5-combinaisons.

Itération suivante : Dans les 792-11=781 autres combinaisons, "regarder pour chacune et la retenir" si au moins 9 de ses triplets ne sont pas déjà vus. donc 119 triplets contenus dans 12 combinaisons. On voit déjà la puissance de l'algorithme ! La 12ème combinaison retenue fournit 9 nouveaux triplets car un des siens était déjà dans les premiers 110 !

3ème itération : Pour être retenue parmi les 792-12=780 autres combinaisons, ne retenir que celles qui contiennent 8 de ses triplets non encore vus. d'oùu une 13ème combinaison retenue et 119+8=127 triplets vus
etc jusquà 9 itérations

J'espère avoir été assez clair, encore que programmer tout cela correctement n'est pas si facile....

Cordialement

yoshi
21-05-2011 13:25:34

Re,

Non, pas clos...
1. Tu n'as pas donné la liste des 32 5-combinaisons...
2. Désolé, mais je présume donc que je dois donc être particulièrement obtus parce que même après :

Pour être clair : C'est un problème de recouvrement de sous-ensembles dans l'ensemble des triplets, les sous-ensembles étant les triplets de chaque conbinaison. Il faut donc partir du maximum de sous-ensembles disjoints pour ensuite réunir avec parcimonie d'autres sous-ensembles ayant le minimum de recouvrement...

donc k progresse de 1 à partir de 0 dans chaque itération, avec un "break" pour stopper les itérations quand le nombre de triplets contenus atteint 220.

pour moi, ça reste très nébuleux à partir de la 2e phrase, parce que les triplets composables à partir des 5-combinaisons, ça je suis capable de les trouver, même à la main (c'est même par là que j'avais commencé, avant même de pythonner)...

Ah qu'il est donc dur de savoir pour soi et en même temps pour les autres ;-)

@+

totomm
21-05-2011 13:05:50

Bonjour,

32, et non 33, est le nombre minimal de 5-combinaisons \(\displaystyle (\ C_{12}^5\ )\) pouvant contenir tous les triplets \(\displaystyle (\ C_{12}^3\ )\) de ces 12 nombres.

il faut égaliser le nombre de fois où chacun des 12 nombres figure dans la première itération (créer les premiers sous-ensembles de triplets disjoints), et la 2ème itération compense alors.

Voici le résultat :
\(\displaystyle (\ C_{12}^5\ =\ 792\ )\)

\(\displaystyle (\ C_{12}^3\ = \ 220\ )\)

itération N° 1  : 110 triplets contenus dans 11  5-combinaisons.
itération N° 2  : 119 triplets contenus dans 12  5-combinaisons.
itération N° 3  : 127 triplets contenus dans 13  5-combinaisons.
itération N° 4  : 162 triplets contenus dans 18  5-combinaisons.
itération N° 5  : 180 triplets contenus dans 21  5-combinaisons.
itération N° 6  : 200 triplets contenus dans 25  5-combinaisons.
itération N° 7  : 208 triplets contenus dans 27  5-combinaisons.
itération N° 8  : 214 triplets contenus dans 29  5-combinaisons.
itération N° 9  : 220 triplets contenus dans 32  5-combinaisons.

Ce problème me semble donc clos. Cordialement

totomm
19-05-2011 11:15:04

Bonjour,

@freddy : Pour une bonne compréhension de la formalisation citée,

freddy a écrit :

au plan formel, il faut compter tous les éléments \(\displaystyle E_k\) de la 5-combinaisons parmi 12 éléments tels que :
\(\displaystyle card(E_i \cap E_j) = 3\)

n'y aurait-il pas possibilité d'avoir aussi des \(\displaystyle E_k\) dont \(\displaystyle card(E_i \cap E_j) = 4\ ou\ même\ 0\) dans les 5-combinaisons donnant le minimum recherché, puisque le triplet choisi peut se trouver dans une seule des 5-combinaisons ?

cordialement

freddy
19-05-2011 10:55:15

totomm a écrit :

Bonsoir,

Si l'on prend les éléments de \(\displaystyle E_{5,12}\) tel que :
\(\displaystyle n_1=1,\;2 \le n_2 \le 11,\;n_5 \ge 12\)
alors Le nombre de 5-combinaisons sélectionnées parmi les 792 est de 120.
les triplets apparaissent tous, et beaucoup une seule fois

Explication ?

cordialement

le terme n2 ne peut pas excéder 9 par construction.

mais je n'ai pas trop de temps pour faire avancer mon smilbllick, donc à plutarque.

totomm
19-05-2011 10:51:46

Bonjour,

Si on forme les 120 combinaisons de 10 nombres (différents) pris 3 à 3 ( \(\displaystyle C_{10}^3\) ) et si on adjoint 2 autres nombres (encore différents) à ces 120, on obtient bien 120 des 792 combinaisons ( \(\displaystyle C_{12}^5\) ) dans une desquelles au moins figurent 3 des 12 nombres choisis au hasard.

Mais cela est encore bien au dessus des 33 combinaisons de 5 nombres trouvées parmi les 792...

@yoshi : Verification prévue OK ?

cordialement

Pied de page des forums

Propulsé par FluxBB