Forum de mathématiques - Bibm@th.net
Vous n'êtes pas identifié(e).
- Contributions : Récentes | Sans réponse
- Accueil
- » Programmation
- » Combinaisons de 12 nombres : triplets
- » Répondre
Répondre
Résumé de la discussion (messages les plus récents en premier)
- yoshi
- 16-09-2011 10:47:59
Salut,
Voilà qui me rassure : mon interprétation personnelle de ta partition ne comportait donc pas de fausse note...
Tu as "juste" rajouté une petite subtilité.
@+
- totomm
- 16-09-2011 10:35:59
Bonjour,
@ yoshi : On obtient d'abord 33, mais certains des 12 nombres apparaissent trop souvent dans le premier choix des 5-combinaisons (au nombre de 12 pour 120 3-combinaisons).
J'ai donc limité, dans le premier choix, à 30 le nombre d'apparition de chacun des 12 nombres : ainsi il n'y a plus que 11 5-combinaisons choisies (pour 110 3-combinaisons)
et en deuxième choix se sélectionne une seule 5-combinaison n'apportant que 9 3-combinaisons nouvelles, mais le nombre d'apparitions de chacun des 12 nombres est suffisamment "homogène" pour obtenir 32 en final sans autre conditionnement que celui du premier choix.
Très subtil en effet, et je ne vois pas comment, après ce genre d'exercice, freddy peut "dédaigner" encore l'utilisation de l'ordinateur...(sa position de principe n'est pas dénuée de fondement, mais est trop rigide, malgré ses connaissances de niveau "supérieur" !)
Cordialement
- yoshi
- 15-09-2011 15:17:30
RE,
Ça y est, j'en ai terminé (provisoirement) avec
* la revue trimestrielle que je devais établir avec découpe du fichier par 2 pages pour envoi à l'éditeur,
* les voyages à Tours (600 km) où j'ai dû chercher un logement, puis emménager ma dernière, étudiante,
* les voyages au Centre de l'Académie d'origine pour essayer de remuer le CROUS, d'obtenir des documents de sa Fac d'origine,
* Mon mal de dos consécutif aux voyages et à "l'enchaisement" dû à la revue
et j'ai pu me pencher sérieusement cette fois sur la réécriture du prog de totomm sur l'idée de base qui est sienne, sans laquelle je n'aurai rien fait : l'indice de coïncidence décroissant du nombre de triplets pas encore rencontrés...
Le voilà (20 min d'écriture et de débogage) :
#!/usr/bin/env python
# -*- coding: cp1252 -*-
def cree_5combi(ni,nj,nk,nl,nm):
L=[]
for i in range(1,ni):
for j in range(i+1,nj):
for k in range(j+1,nk):
for l in range(k+1,nl):
for m in range(l+1,nm):
L.append([i,j,k,l,m])
return L
def cree_3combi(nk,nl,nm):
M=[]
for i in range(1,nk):
for j in range(i+1,nl):
for k in range(j+1,nm):
M.append([i,j,k])
return M
def cree_Indices():
Idc=[]
for i in range(0,3):
for j in range(i+1,4):
for k in range(j+1,5):
Idc.append([i,j,k])
return Idc
def eclate_5combinaison(Idc,T):
L=[]
for i in range(10):
m,n,p=Idc[i]
L.append([T[m],T[n],T[p]])
return L
n,p=12,5
ni=n-p+2
nj=n-p+3
nk=n-p+4
nl=n-p+5
nm=n-p+6
# Initialisations
L512=cree_5combi(ni,nj,nk,nl,nm)
n512=len(L512)
L312=cree_3combi(nk,nl,nm)
n312=len(L312)
Indices=cree_Indices()
Vues_3,Vues_5=[],[]
C5=L512[:] # Crée une copie des 792 combinaisons de 5 parmi 12
# Traitement
for i in range(10,0,-1): # maximum décroissant de triplets communs
for combi in C5: # Extrait chaque 5combinaison de la liste C5
# extrait les 10 triplets de 3 parmi 5
M312=eclate_5combinaison(Indices,combi)
diff=0
# Examine chacun des 10 triplets extraits de la 5combi en cours
for trp in M312:
# Incrémente le compteur à chaque triplet non déjà stocké
if trp not in Vues_3:
diff+=1
if diff==i: # Si le compteur est égal au maximum accepté
# Passe en revue chaque triplet extrait plus haut
for j in range(10):
# Si le triplet n'a pas déjà été enregistré
if M312[j] not in Vues_3:
# Stockage du triplet
Vues_3.append(M312[j])
# Stockage de la 5combinaison
Vues_5.append(combi)
# suppression de la 5combinaison de la liste globale
del C5[C5.index(combi)]
print len(Vues_5)
Tout va bien alors ?
Non, pas complètement :
* Il me semble me souvenir que le prog de totomm est plus rapide
* Je tombe sur 33 (!) 5combinaisons : je les ai testées en les éclatant : ça colle, j'ai bien 220 triplets différents de 3 nombres pris sur 12...
Donc, il me reste encore à chercher pourquoi j'ai une 5combinaison de trop...
C'est quand même bizarre, : il n'y a aucune raison logique pour que mon prog donne combinaison de trop et c'est pourtant le cas..
Je vais dans un premier temps chercher laquelle par comparaison de mes résultats avec ceux de totomm.
Ensuite, nanti de ce sésame, j'espère que je trouverai pourquoi.
Si quelqu'un avait l'illumination avant moi, qu'il ne se gêne pas pour pointer la cause du problème : je n'en serais pas choqué, n'ayant pas la science infuse... ;-)
@+
[EDIT]
Petit détail...
Pourquoi écrire
C5=L512[:] et non simplement C5=L512
A cause d'une particularité Pythonesque, qu'on en juge :
>>> A=[1,2,3]
>>> B=A
>>> B[0]=0
>>> A
[0,2,3]
Surprenant, hein ?
C'est que B=A crée non pas un 2e objet, mais donne un 2e nom au même objet...
Mais :
>>> A=[1,2,3]
>>> B=A[:]
>>> B[0]=8
>>> A
[1,2,3]
>>> B
[8,2,3]
Etait-il bien utile de créer un 2e objet_liste ?
Oui, par économie de pensée parce qu'habitude qui peut éviter des surprises dans d'autres prog...
Non, ici, je ne réutilise pas ultérieurement ma liste de 792 5combinaisons
- freddy
- 14-09-2011 10:22:34
Salut tomtom,
bien sûr que j'ai compris la méthode, même si ce n'est pas comme cela que je l'aurais expliquée.
Je voulais expliciter l'esprit plus général de la méthode de manière plus formelle, mais les explications fournies devraient suffire au lectorat du site.
Pour le 36 (du Quai des Orfèvres ? ;-) ), je te laisse réfléchir encore un peu.
- totomm
- 14-09-2011 08:36:59
Bonjour,
@freddy : Mieux vaudrait dire simplement si vous avez compris la méthode d'après le dernier exposé, et publier à votre tour le comment de :
On sait qu'on doit trouver au plus 36 5-grilles
quand au reste, c'est sans doute toujours ce que le modérateur écrivait :
...trait d'humour freddyesque...
et s'épancher comme cela n'a aucun intérêt.
Cordialement
- freddy
- 13-09-2011 22:30:26
Bonjour,
freddy a écrit :A propos : cordial ment !
Ce genre de mot d'esprit méchant et totalement injustifié ne devrait pas apparaitre sur ce Forum !
freddy, vous avez sûrement mieux à publier !A demain, peut-être, Cordialement.
Salut,
amusant de constater comment il faut faire pour te "pousser" à expliquer ...
Quant à mon "A propos", il en va de ton "cordialement" comme du "Comment allez vous " ou "comment vas tu" : en fait, on se fiche éperdument de la réponse dans 99,9 % des cas.
Pour les 0,1 % restant, la question est sincère et attend une vraie réponse, mais elle est réservée à nos amis, ceux qu'on aime.
Le "cordialement" systématique, voire automatique, n'a rien de cordial (consulter le sens de ce mot pour comprendre), il se veut la marque d'une éducation qui manque en vérité d'authentique chaleur humaine .
Ta réaction montre que le trait a atteint sa cible : tu as bien compris ce que je dénonçais ... On dirait aujourd'hui : ce que je stigmatisais.
Pour finir, je ne pense pas que tu aies encore gagné tes galons pour être le censeur de notre communauté, donc évite de dire aux modos ce qu'ils doivent faire, ils le savent mieux que quiconque sur ce site.
Bien à toi, mon grand.
- yoshi
- 09-09-2011 20:11:01
Bonsoir,
Je rejoins totomm. Par rapport à l'utilisation d'un tableur, un langage de programmation t'offre une souplesse et une liberté sans égales...
Le revers de la médaille, c'est que dans le tableur, une partie du travail est prémâché (fonctions élaborées préfinies) alors que avec le langage de programmation, tu dois te créer tes propres fonctions...
Mais justement, devant les créer, tu les conçois à ton goût !
Bref, un langage de programmation comme Python, n'est pas trop verbeux, et (en principe) si tu le maîtrises tu dois pouvoir comprendre de quoi il retourne par simple lecture....
Je reprend un de mes programmes fait pour stormin.
La problématique était :
Je voudrais faire la somme des éléments de la matrice,si la somme est >0,je remplace le max par 0,et si la somme est <0,je remplace le min par 0, jusqu'à avoir une somme égale à zéro.
Voici le programme (valable que pour des entiers) :
(En Python c'est l'indentation qui détermine les blocs de programmes)
#!/usr/bin/env python
# -*- coding: Latin-1 -*-
# v. 2.0
# Données de la matrice
L=[-5,2,3,-7,6,2,8,1,3,4,0,-9,1,-55,4,3]
# Dimension de la matrice : nb de lignes, nb de colonnes
m,n=4,4
dim=m*n
# Initialistion de la somme (n'importe quelle valeur autre que zéro convient)
somme=1
# Affichage matrice d'origine
print "Matrice initiale :"
for j in range(dim):
if j%n==0 and j>0:
print "%3i" % L[j],
print "Sommes successives :"
while somme !=0:
# Calcul de la somme
somme=sum(L)
print somme,
# test de valeur et relevé de la position du mini ou du maxi
if somme > 0:
pos=L.index(max(L))
elif somme<0:
pos=L.index(min(L))
# mise à zéro du nombre en position pos relevée
L[pos]=0
print "Matrice modifiée :"
for j in range(dim):
if j%n==0 and j>0:
print "%3i" % L[j],
Dans ce programme, j'ai essayé de faire simple.
Je n'avais pas envie de m'embêter avec les questions sur les données...
J'ai donc écrit la matrice sous forme d'une liste ligne par ligne à la suite...
Ensuite connaissant le nombre de lignes et de colonnes, je calcule le nb d'éléments...
Puis via une boucle qui va faire dim tours, j'affiche mes 16 éléments 4 par 4, chacun occupant 3 espaces (rôle du "%3i")
Comme il ya une virgule en fin d'instruction, l'affichage se fait sur la même ligne, donc lorsque j'arrive en bout de ligne (de matrice), j'ajoute un print, pour forcer le passage en ligne suivante.
Puis je laisse deux lignes vides.
Puis je teste la somme des éléments de la matrice : tant que somme différente (!=) de 0, je demande la somme des éléments (et je l'affiche pour contrôle).
Une fois la somme calculée :
* si elle est strictement positive, je relève la position du maximum
* sinon si elle est strictement négative, je relève la position du minimum.
Ensuite que ce soit un mini ou un maxi, le nombre en position pos dans ma liste est égalé à 0.
Lorsque la somme n'est plus différente de 0, ma condition n'est plus vérifiée, et je sors de la boucle pour afficher la nouvelle matrice.
Voilà l'affichage obtenu :
-5 2 3 -7
6 2 8 1
3 4 0 -9
1 -55 4 3
Sommes successives :
-39 16 8 2 -2 7 3 0
Matrice modifiée :
-5 2 0 -7
0 2 0 1
3 0 0 0
1 0 0 3
Voilà, jpp !
T'as pigé ?
Bon, il y a d'autres façons d'écrire ça...
J'avais commencé par représenter la matrice sous la forme d'une liste de listes, mais stormin n'a pas aimé : il y avait trop de boucles, alors j'ai refait autrement...
Et je suis bien sûr que totomm ferait ça encore autrement.
Ce programme est écrit en Python 2.6.5, totomm travaille avec la version 3.2 (qq petits changements)...
Je garde 2.6.5 notamment pour 2 raisons :
- il existe un accélérateur de calculs (écrit en C) pour Python jusqu'à 2.7 exclu...
- il existe des petits programmes permettant de "compiler" un programme Python, le rendant indépendant de la présence du logiciel Python sur la machine hôte jusqu'à, sauf erreur, la v. 2.7...
- il existe de nombreuses "bibliothèques" (des modules) qui n'ont pas été portés sous Python 3.x.
Je passerai à Python 3.x lorsque ce sera fait...
Allez vas-y, essaie Python : http://www.python.org/download/releases/
Un bouquin (gratuit et libre) à télécharger pour les débuts :
* Python 2.x : http://inforef.be/swi/download/apprendre_python.pdf
* Python 3.x : http://inforef.be/swi/download/apprendre_python3.pdf
@+
- totomm
- 09-09-2011 15:21:54
Bonjour,
Il y a une chose que je ne comprends pas, pourquoi le minimum est 32 et pas [tex]\binom{12}{3}/\binom{5}{3}[/tex] =22 ?
Parce qu'il y a 220 triplets (les 3-combinaisons) et que 22 5-Combinaisons ne peuvent les donner que si ces 3-Combinaisons étaient TOUTES différentes, ce qui ne peut être.
Preuve intuitive : Dans les 220 triplets les 12 nombres de départ figurent chacun 55 fois (chacun autant de fois). Dans 22 5-combinaisons il y a 110 nombres = 2x5x11. donc les 12 nombres ne figurent pas chacun autant de fois !
Donc il faut plus que 22 5-combinaisons pout retrouver chacune des 3-combinaisons au moins une fois.
En fait, dans les 320 3-combinaisons données par les 32 5-combinaisons, il y a 136 des 220 3-combinaisons données une seule fois, 71 données 2 fois, 10 données 3 fois, et 3 données 4 fois. (facile à voir sous Python)
c'est bien compliqué, mais...ne peut mieux faire que 32 !
Cordialement
- Golgup
- 09-09-2011 14:29:45
salut,
Il y a une chose que je ne comprends pas, pourquoi le minimum est 32 et pas [tex]\binom{12}{3}/\binom{5}{3}[/tex] =22 ?
- totomm
- 09-09-2011 14:28:18
Bonjour,
@ jpp : lancez-vous avec Python si vous avez quelques moments disponibles : Il existe des tutoriels assez simples et sûrement yoshi saurait vous conseiller la meilleure démarche...
Vous serez toujours soutenu sur ce forum, car, comme pour tout, le démarrage est assez ingrat, quoique pas trop difficile...
Cordialement
- jpp
- 09-09-2011 12:54:10
Salut à tous.
ça me rappelle un problème que j'avais voulu résoudre il y quelque temps déjà; et qui consistait à écrire 6
sextuplets avec 6 chevaux choisis dans un pari , qui permettait d'avoir le tiercé dans l'ordre une fois parmi
un des 6 sextuplets puisque [tex]A_6^3 = 120[/tex], [tex]C_6^3 = 20[/tex] et [tex]A_3^3 = 6[/tex]
je me retrouvais systématiquement avec 2 triplets ordonnés identiques et évidemment il m'en manquait par ailleurs
et ceci en effectuant des symétries .
pour revenir à votre problème , pour avoir une seule fois chaque tous les triplets il faudrait optimiser en trouvant
22 quintuplets si j'ai bien compris. Mais , n'ayant jamais programmé je suis bien incapable de trouver n(quintuplets)<32
à plus.
- totomm
- 09-09-2011 11:33:06
Bonjour,
un trait d'humour freddyesque... que je n'ai d'ailleurs pas compris :-(
Mieux vaut ne pas comprendre....
Quant au programme, je n'ai pas eu le temps de me repencher dessus, mais ça va venir...
Pour mieux comprendre :
Hors tout langage de programmation, voici le détail de la méthode suivie pour aboutir à un minimum de 32 :
Soient les 792 5-combinaisons de 5 nombres parmi 12
Soient les 220 3-combinaisons de 3 nombres parmi les 12
Une 5-combinaison contient 10 des 3-combinaisons : Comment choisir un minimum de 5-combinaisons contenant toutes les 220 3-combinaisons ?
Méthode : commencer par choisir des 5-combinaisons dont les 10 3-combinaisons sont toutes différentes. On peut en trouver 12. Mais, dans cette première étape, l'idéal serait que chacun des 12 nombres apparaisse 30 fois. En veillant à ce qu'aucun nombre n'apparaisse pas plus de 30 fois on trouve 11 5-combinaisons, que l'on marque comme "retenues", qui contiennent 110 3-combinaisons toutes différentes que l'on marque comme "vues"
[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]
Parmi les 5-combinaisons non encore "retenues", on choisit ensuite celles dont 9 des 10 3-combinaisons ne sont pas encore marquées "vues" et sont toutes différentes
On en trouve 1 qui conduit à 12 5-combinaisons "retenues" et 119 3-combinaisons "vues"
[2, 5, 6, 9, 10]
puis celles dont 8 des 10 3-combinaisons ne sont pas encore marquées "vues" et sont toutes différentes :
1 conduit à 13 5-combinaisons "retenues" et 127 3-combinaisons "vues"
[1, 3, 4, 8, 11]
puis celles dont 7 des 10 3-combinaisons ne sont pas encore marquées "vues" et sont toutes différentes :
5 conduisent à 18 5-combinaisons "retenues" et 162 3-combinaisons "vues"
[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]
puis celles dont 6 des 10 3-combinaisons ne sont pas encore marquées "vues" et sont toutes différentes :
3 qui conduisent à 21 5-combinaisons "retenues" et 180 3-combinaisons "vues"
[1, 4, 5, 9, 11], [1, 6, 7, 10, 11], [2, 3, 8, 9, 10]
puis celles dont 5 des 10 3-combinaisons ne sont pas encore marquées "vues" et sont toutes différentes :
4 qui conduisent à 25 5-combinaisons "retenues" et 200 3-combinaisons "vues"
[2, 3, 5, 6, 11], [2, 5, 7, 8, 12], [3, 4, 5, 8, 12], [3, 9, 10, 11, 12]
puis celles dont 4 des 10 3-combinaisons ne sont pas encore marquées "vues" et sont toutes différentes :
2 qui conduisent à 27 5-combinaisons "retenues" et 208 3-combinaisons "vues"
[1, 7, 8, 9, 10], [3, 4, 6, 7, 9]
puis celles dont 3 des 10 3-combinaisons ne sont pas encore marquées "vues" et sont toutes différentes :
2 qui conduisent à 29 5-combinaisons "retenues" et 214 3-combinaisons "vues"
[1, 2, 6, 10, 12], [5, 6, 7, 9, 12]
puis celles dont 2 des 10 3-combinaisons ne sont pas encore marquées "vues" et sont toutes différentes :
3 qui conduisent à 32 5-combinaisons "retenues" et 220 3-combinaisons "vues"
[1, 2, 8, 11, 12], [1, 4, 5, 6, 10], [4, 7, 8, 10, 11]
peut-on faire moins de 32 ?
Cordialement.
- yoshi
- 09-09-2011 10:00:47
Re,
Méchant ?
Bof, je ne crois pas... Juste un trait d'humour freddyesque... que je n'ai d'ailleurs pas compris :-(
Quant au programme, je n'ai pas eu le temps de me repencher dessus, mais ça va venir...
@+
- totomm
- 09-09-2011 08:45:44
Bonjour,
A propos : cordial ment !
Ce genre de mot d'esprit méchant et totalement injustifié ne devrait pas apparaitre sur ce Forum !
freddy, vous avez surement mieux à publier !
A demain, peut-être, Cordialement.
- freddy
- 08-09-2011 23:01:10
Salut !
je vais faire sibyllin, comme tontonm : Eurêka !
Oui, je sais, c'est un peu court en somme, mais je ne sais pas faire mieux que tontonm.
Donc je récapépète : Eurêka !
J'esspliquerais demain, peut être.
A propos : cordial ment !