Combinaisons de 12 nombres : triplets

totomm · 27-08-2011 09:37:01

Bonjour,

Ci-dessous mon code à la demande de freddy.
cordialement

# Python 3.2  
# Programme créé par totomm (Bibmath) pour traiter le problème
# "Combinaisons" posé par Fayrouse le 12-05-2011 dans le "Café Mathématique"

# soient les nombres Compris Entre 1 Et 12 (1-2-3-4-5-6-7-8-9-10-11-12)

# Etablir: 1-Toutes Les Combinaison Possibles des 5 nombres parmi les 12.

# 2-le Nombre minimal de ces Combinaisons de telle sorte

# que tout triplet de 3 de ces nombres soit contenu au moins une fois

# dans au moins une combinaison

# Combinaisons de n objets pris p à p (5 objets parmi 12)

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=[] # 3 objets parmi 12

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("5 nombres parmi 12 =",len(list12_5))

print("3 nombres parmi 12 =",len(list12_3))

# Idée pour la question 2 :

# Itérer pour ne retenir que les 5-combinaisons qui contiennent le maximum

# de triplets "non encore vus"

# former les 10 triplets de chaque 5-combinaison de list12_5

# et marquer chacun présent si leur 5-combinaison est retenue

#Initialisations

présents=[0]*len(list12_3) # contiendra 1 pour chaque triplet "vu"

nbfois=[0]*13 # marque le nombre de fois où un nombre nb figure

              # dans les triplets "déjà vus" dans les 5-combinaisons retenues

combRetenus=[] # liste des 5-combinaisons composant le minimum cherché

nbT=0 # nombre de triplets "vus" au fur et à mesure de l'itération

for k in range(0,15): # itération pour retenir de nouvelles 5-combinaisons

    if nbT==len(list12_3):break # Condition d'arrêt

    for n in range(0,len(list12_5)):

        comb=list12_5[n]

        if comb not in list(combRetenus): #prendre chaque 5-combinaison non encore retenue

            tripletsComb=[]

            for a in range(0,3):

                for b in range(a+1,4):

                    for c in range(b+1,5):

                        triplet=[comb[a],comb[b],comb[c]]

                        tripletsComb.append(triplet)

            #print(tripletsComb)

            TnonInclus=0

            for p in range(0,10):

                i=list12_3.index(tripletsComb[p])

                if présents[i]==0:

                    TnonInclus +=1

            if (10-TnonInclus) == k:

                # Essai d'égalisation entre nombres quand k==0

                combOK=1

                if k==0: # Mettre ici 15 au lieu de 0 entraine 33 5-Combinaisons

                    for p in range (0,10):

                        if nbfois[tripletsComb[p][0]] == 30: combOK=0

                        if nbfois[tripletsComb[p][1]] == 30: combOK=0

                        if nbfois[tripletsComb[p][2]] == 30: combOK=0

                if combOK==1:

                    for p in range(0,10):

                        i=list12_3.index(tripletsComb[p])

                        if présents[i]==0:nbT+=1

                        présents[i] += 1

                        nbfois[tripletsComb[p][0]] += 1

                        nbfois[tripletsComb[p][1]] += 1

                        nbfois[tripletsComb[p][2]] += 1

                    combRetenus.append(comb)

    print("itération N°",k+1," :",nbT,"triplets contenus dans",len(combRetenus)," 5-combinaisons.")

print("nombre de triplets contenus =",nbT,"   vus ce nombre de fois :")

print(présents)

print("Les nombres sont vus", nbfois)

print()

print("Nombre de 5-combinaisons retenues =",len(combRetenus))

print(combRetenus)

print("fin")

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)

print("Fin de vérification")

Edit Fred :

J'ai modifié ta balise code pour activer la coloration syntaxique comme elle est désormais permise par le forum.
Pour colorer les programmes Python, il faut écrire [ code=python] (tu avais ajouté la version...)

Edit totomm :
Merci Fred, Précédemment j'avais piégé les utilisateurs en passant de 2.7 à 3.2 sans rien dire...Je mets maintenant la version en tête du code.

Dernière modification par totomm (28-08-2011 07:59:26)

freddy · 27-08-2011 17:14:05

Salut et merci.

Je ne connais pas Python, mais je sais que tu sais coder en VBA. Tu pourrais le poster, stp ?

D'avance, merci.

Je travaille sous SAS et n'ai pas encore eu le trait de génie pour trouver la bonne manip' !!!

totomm · 28-08-2011 07:55:00

Bonjour,

Je me suis mis à Python sur l'insistance de Yoshi et ne le regrette pas...C'est si simple !

Je peux programmer en Visual Basic 2008 Express. VBA est un VB pour une application telle que Word, Excel, Access et le problème est d'abord de choisir comment éditer les résultats. Je suis limité à "microsoft office 2000" et pour être plus à jour, je devrais passer via la programmation "OpenOffice"

Sous Python l'interpréteur Idle GUI fournit la fenêtre où publier les résultats, Sous VB Express il faut construire sa fenêtre et y incorporer une textBox ; et il faut avoir installé le "Microsoft Framework.net 3.0 ou 3.5 (gratuit lui aussi) pour exécuter les programmes écrits en VB, C++, C3 etc
Peut-être faudrait-il que j'essaie de décrire plus complètement l'algorithme qui est assez simple (Voir ligne 28 ci-dessus), bien que le programme soit commenté au mieux...

Sans doute Yoshi saurait conseiller utilement car je ne connais pas du tout les services et applications dont vous disposez avec SAS.

Restant disponible,Cordialement

freddy · 28-08-2011 14:02:03

Salut et merci.

J'ai bien l'idée de la procédure depuis le début, mais je n'arrive pas à la mettre en œuvre sous SAS. Pas grave, je finirai bien par trouver.

Sous VBA, je finirai aussi bien par trouver. Ce que je voudrais est concevoir une approche formelle pour connaître la réponse selon les valeur de n, p et q. Je sais que c'est assez velu. Pour ma retraite, si j'y arrive un jour ...
Bb

yoshi · 28-08-2011 14:38:10

Salut,

Je me dévouerais bien pour t'expliquer ça en pseudo-code, mais je dois reconnaître hélas que le coeur de l'algo lignes 42 à 75 marche très bien, mais que en simple(s) lecture(s) comme ça, je suis toujours incapable de comprendre ce qu'il y bricole.
Aie ! Maintenant, c'est dit ! Tant pis, je vais de nouveau déclencher l'ire de totomm, sur la mauvaise volonté que j'y mets, mais c'est comme ça...
Et vu que lui dit que ce qu'il a fait est très simple, j'ai plus qu'à chercher un trou de souris pour m'y cacher...

Par exemple.
Ligne 42
ça commence déjà mal : pourquoi 15 ? pourquoi pas 8 ou 10 ?
# itération pour retenir de nouvelles 5-combinaisons : comment ça "de nouvelles 5-combinaisons" ?.
Pour les deux premières séries de boucles (avant la ligne 42) nous sommes en phase :
792 combinaisons de 5 sur 12 et 220 combinaisons de 3 sur 12.
D'où ma question : pourquoi de "nouvelles combinaisons" ? Il y en aurait donc d'autres en dehors des 792 ?

Lignes 48 à 52.
Là par contre, il me semble comprendre que c'est la construction du fichier nommé chez moi Indices :
[a,b,c,d,e] étant une liste à 5 éléments quelconques indicée [0,1,2,3,4] on recherche l'ensemble des combinaisons de 3 sur 5 de ces indices.
Ainsi quels que soient les éléments a,b,c,d,e de départs, grâce à ce fichier de combinaisons d'indices, on peut éclater facilement chaque 5-combinaison en ses 10 3-combinaisons.
C'est ainsi que j'ai procédé pour vérifier que le nombre de 5-combinaisons retenues, et données par totomm, était suffisant, i.e qu'en les éclatant, en les triant et en supprimant doublons, triplons etc... on retrouvait bien 220 combinaisons de 3 pris sur 12...
J'ai écrit "il me semble comprendre" parce que si cette construction fait partie de la boucle aux 15 itérations (au lieu d'être en amont), il doit y avoir une bonne raison que je ne vois pas...

La solution serait que je fasse tourner et que je pose des "mouchards" partout pour voir ce qui s'y fait et à quel moment.
Pour l'instant, je n'ai pas ce courage et d'autres fers au feu dont ma conjugaison, pour laquelle faute de comprendre (encore !) ce que j'ai bien pu imaginé il y a 35 ans (des fois, je suis carrément pas d'accord avec ce qui est écrit : pourtant il marche !), j'ai carrément inventé une autre algorithmique...
Lorsque j'aurai fini le codage du 3e Groupe, ça marchera (presque !) du premier coup...
Je m'étais accordé une récréation avec le codage/décodage "railfence"...
Terminé... Assez ri !
Mon mois de septembre s'annonce chargé. Je pourrai souffler après.

@+

totomm · 28-08-2011 17:20:06

Bonjour,

ci-dessous, après les observations de freddy et Yoshi :
J'ai remanié "tous" les commentaires et tenté de bien expliquer la démarche du programme (lignes 31 à 52)
Je ne ferais pas mieux en VB, mais je ferai si freddy le redemande...
J'essaierai aussi de ne plus dire que je fais des choses simples. J'essaierai...

à partir de la ligne 100, c'est un simple contrôle supplémentaire

il est bien vrai que l'on croit avoir "bien commenté", mais quand on se relit après quelque temps, on voit un tas de manques...

Cordialement

# Python 3.2  
# Programme créé par totomm (Bibmath) pour traiter le problème
# "Combinaisons" posé par Fayrouse le 12-05-2011 dans le "Café Mathématique"

# soient les nombres Compris Entre 1 Et 12 (1-2-3-4-5-6-7-8-9-10-11-12)

# Etablir: 1-Toutes Les Combinaison Possibles des 5 nombres parmi les 12.

# 2-le Nombre minimal de ces Combinaisons de telle sorte

# que tout triplet de 3 de ces nombres soit contenu au moins une fois

# dans au moins une combinaison

# Création de la liste des 5-combinaisons (5 nombres pris parmi 12)

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])

# Création de la liste des 3-combinaisons (3 nombres pris parmi 12)

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 :") # imprimer le nombre de 5 et de 3-combinaisons

print("5 nombres parmi 12 =",len(list12_5))

print("3 nombres parmi 12 =",len(list12_3))

# Idée pour la question 2 :

# il faut créer une liste des 5-combinaisons qui vont être retenues

combRetenus=[] # Cette liste est initialement vide

# Quand une 5-combinaison sera retenue en parcourant la liste list12-5

# on marquera à 1 ses 10 triplets.

# Pour ce faire on crée une liste initialisée à 0

présents=[0]*len(list12_3) # chaque élément correspond à un triplet de list12-3

# Il faut aussi compter le nombre de triplets "vus" (mis à 1 dans la liste présents)

nbT=0

# pour affiner le résultat, il faut compter dans la liste nbfois

#  le nombre de fois où un des 12 nombres figure dans les triplets "déjà vus"

nbfois=[0]*13 # initialement à 0

# il faut maintenant parcourir plusieurs fois la liste12-5 des 5-combinaisons

# la première fois on retiendra les 5-combinaisons dont les 10 triplets

# ne sont pas encore vus (marqués à 1 dans la liste présents)

# la seconde fois on retiendra les 5-combinaisons dont seulement 9 triplets

# ne sont pas encore vus

# puis 8, 7 ....le programe s'arrètera forcément !

for k in range(0,10):

# itération pour retenir les combinaisons ayant 10-k triplets non vus

    if nbT==len(list12_3):break # Condition d'arrêt

    for n in range(0,len(list12_5)): # parcourir la liste des 5-combinaisons

        comb=list12_5[n]

        if comb not in list(combRetenus): # 5-combinaison non encore retenue

            tripletsComb=[] # créer la liste de ses triplets

            for a in range(0,3):

                for b in range(a+1,4):

                    for c in range(b+1,5):

                        triplet=[comb[a],comb[b],comb[c]]

                        tripletsComb.append(triplet)

            # Compter combien des 10 triplets ne sont pas encore dans présents

            totalTripletsNonInclus=0

            for p in range(0,10):

                i=list12_3.index(tripletsComb[p]) # récupérer l'index du triplet

                #pour vérifier dans présents

                if présents[i]==0:

                    totalTripletsNonInclus +=1

            if totalTripletsNonInclus == 10-k:# tester pour retenir la 5-combinaison

                # Essai d'égalisation entre nombres quand k==0

                combOK=1

                if k==0: # Mettre ici 15 au lieu de 0 entraine 33 5-Combinaisons

                    for p in range (0,10):

                        if nbfois[tripletsComb[p][0]] == 30: combOK=0

                        if nbfois[tripletsComb[p][1]] == 30: combOK=0

                        if nbfois[tripletsComb[p][2]] == 30: combOK=0

                if combOK==1: # toujours vrai sauf éventuellement pour k==0

                    for p in range(0,10):

                        # marquer les triplets dans présents

                        i=list12_3.index(tripletsComb[p]) # récupérer l'index

                        if présents[i]==0:nbT+=1 # compter le nombre de triplets

                        présents[i] += 1

                        # compter pour chacun des nombres dans les triplets

                        nbfois[tripletsComb[p][0]] += 1

                        nbfois[tripletsComb[p][1]] += 1

                        nbfois[tripletsComb[p][2]] += 1

                    combRetenus.append(comb) # et insérer la 5-combinaison

    print("itération N°",k+1," :",nbT,"triplets contenus dans",len(combRetenus)," 5-combinaisons.")

print("nombre de triplets contenus =",nbT,"   vus ce nombre de fois :")

print(présents)

print("Les nombres sont vus", nbfois)

print()

print("Nombre de 5-combinaisons retenues =",len(combRetenus))

print(combRetenus)

print("fin")

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)

print("Fin de vérification")

freddy · 31-08-2011 11:02:45

Salut totomn,

je ne sais si c'est la chaleur ou le café, je ne comprends rien à ta méthode de sélection de 5-grilles nécessaires et suffisantes pour retrouver les 220 3-grilles de nombre parmi 12.

Pourrais tu stp m'expliquer de façon simple comment tu fais, merci.

On sait qu'on doit trouver au plus 36 5-grilles, tu arrives à 32 (j'ai vérifé, les grilles que tu donnes sont parfaites), mais j'avoue avoir du mal à me concentrer pour comprendre ta méthode de sélection.

je serais heureux ce soir de pouvoir me coucher en ayant compris. Ensuite, je te proposerais un autre petit sujet.

totomm · 01-09-2011 09:24:15

Bonjour,

Relisez les lignes 47 à 52 en buvant du thé bien glacé, tout deviendra clair :-))

et dans un premier temps ne tenez pas compte des lignes 74 à 81, parce que là, cela devient difficile !!! lol

freddy · 01-09-2011 10:40:24

totomm a écrit :

Bonjour,
Relisez les lignes 47 à 52 en buvant du thé bien glacé, tout deviendra clair :-))
et dans un premier temps ne tenez pas compte des lignes 74 à 81, parce que là, cela devient difficile !!! lol

Salut,
adepte de Nicolas Boileau (tiens, encore un Nicolas) je tiens pour acquis le sage principe selon lequel :

"ce qui se conçoit bien s'énonce clairement,
et les mots pour le dire arrivent aisément"

C'est d'ailleurs la devise de tous les pédagogues de la planète !

So I'm still waiting !

totomm · 02-09-2011 10:01:00

Bonjour,

@ freddy : Absolument d'accord. Cette méthode bien conçue est énoncée clairement dans ce programme.
vous reconnaissez d'ailleurs la perfection de son résultat !
Dites exactement à partir de quelle ligne du programme vous n'arrivez plus à vous concentrer suffisamment pour comprendre, et je pourrai alors essayer de vous aider...avec mes pauvres moyens pédagogiques ...

Cordialement

freddy · 02-09-2011 15:29:09

Salut,

ben ... tout : je ne comprends pas l'esprit de la méthode de l'idée pour répondre à la question 2. Après ce n'est qu'un problème de construction du pgm fonction de la logique de sélection retenue, à condition de l'avoir comprise.

Maintenant si autre une âme charitable veut bien m'expliquer, je lui en sais déjà infiniment gré.

totomm · 02-09-2011 17:10:00

Bonjour,

Après Boileau, citons Gaston Bachelard : "...Il peut exister, chez un individu, des barrages intellectuels qui s'opposent à l'évolution de sa pensée, soit parce qu'ils appartiennent à des théories anciennes en contradiction avec les faits présents, soit parce qu'ils s'opposent au style de pensée de l'individu concerné...."

Attendons l'âme charitable...

Cordialement

yoshi · 02-09-2011 17:52:11

Salut,

Si je puis permettre, cette citation de Bachelard, peut tout aussi bien se retourner contre celui qui en use.
Je la trouve même, personnellement, parfaitement déplacée du point de vue de celui ou ceux qui ne comprennent pas...
J'augurerais mal de l'avenir d'un prof de maths disant à ses élèves :
<< Ma démonstration est parfaite, je n'ai rien à ajouter. Vous n'avez pas compris ? Réfléchissez mieux ! >>
J'y vois une façon ô combien plus délicate de stigmatiser la mauvaise volonté supposée...

Je me lance donc (par intermittences, parce que j'ai une revue à boucler)...
J'ai emprunté du matériel de spéléo pour partir en exploration.
Je procède ainsi que toujours.
1. Pour l'instant, j'ai modifié la première boucle contrôlée par la variable k pour qu'elle ne produise qu'une seule itération.
2. Je lis le commentaire :
# itération pour retenir les combinaisons ayant 10-k triplets non vus
Donc, j'en infère que pour k == 0, on ne va retenir que les 5_combinaisons ayant 10/10 triplets non vus.
3. Nanti de cette info, je lance le prog.
Ce que je vois est conforme à ce que j'attendais [1,2,3,4,5] est retenu...
Conforme à ce que j'attendais, oui mais jusqu'à [1,2,6,7,8] seulement !
Parce qu'à partir de là, ça se gâte : en effet dès [1,2,6,7,9], je vois que la liste des 5 combinaisons retenues, s'enrichit d'un élément.
Et là, ça m'interpelle : avec [1,2,6,7,8] je peux composer 10 triplets dont 9 n'ont pas été vus dans [1,2,3,4,5], et pas 10 ! Alors ?

Quand j'aurais compris, je referais ce que j'ai déjà fait une fois : récrire ce programme autrement pour être sûr d'avoir compris.

@+

[EDIT]
J'ai intercalé cette ligne-mouchard entre les lignes 72 et 73 :
print " ",n,combRetenus,présents.
Donc, j'affiche l'état précédent du combRetenus...
Mais ça n'explique pas le fait que la première itération (k==0) retienne [1,2,3,4,5] puis] puis...
Ceci se produisant pour n=86 qui montre que à n=85 a été retenu [1,2,6,7,8]...

[EDIT2]
Je n'ai rien dit...
Oui, d'accord TRI-plets, moi, je m'étais focalisé sur les nombres 1 et 2...
[1,2,6,7,8] vient juste après [1,2,5,11,12] et là, on trouvait [1,2,5] commun.
Je vais pouvoir poursuivre...

Dernière modification par yoshi (02-09-2011 18:53:11)

freddy · 02-09-2011 17:54:00

Re,

puisque nous en sommes à étaler notre confiture, je citerai volontiers René Thom pour m'aider à plaider ma cause :

" Est rigoureuse toute démonstration, qui, chez tout lecteur suffisamment instruit et préparé, suscite un état d'évidence qui entraîne l'adhésion."

Tu vois mieux ?

Il y a dans le forum un sujet qui a fait couler beaucoup d'encre, car nous nous opposions sur l'établissement d'un résultat à un joli problème géométrique soluble par un calcul informatique.

A la fin, nous nous sommes aperçus que l'erreur de raisonnement de certains reposait sur erreur de lecture (voire de compréhension) de l'énoncé...

Pour moi, il est impossible qu'on n'arrive pas à se comprendre. Il y a nécessairement une manière d'expliquer sa façon de raisonner qui permet de la rendre intelligible à tous. Quand quelqu'un me dit : "je ne comprends pas ce que vous dites", je cherche toujours à reformuler pour que mon idée devienne compréhensible, et qu'on puisse l'examiner plus avant pour vérifier si elle est utilisable ou non.

Manifestement, tu as toujours compris ce qu'on t'expliquait et tu n'as jamais eu besoin de faire reformuler. Tu as eu la chance d'avoir de très bons maîtres.

Rien de grave pour autant, je trouverai bien tout seul.

Salut

[EDIT]
Salut yoshi, je suis d'accord, la citation se retourne d'elle même :-)))

Dernière modification par freddy (02-09-2011 17:55:46)

yoshi · 02-09-2011 19:12:34

Re,

Donc, je vais arriver à comprendre...
Mais moi, amateur de Python, j'ai Python installé, ça me facilite les choses ^_^, s'pas...
A la décharge de freddy, ce n'est pas son cas : pourquoi devrait-il installer Python pour décoder ton prog ?
Lorsque tu as publié ton 1er prog en VB, pour le traduire en Python, je n'ai pas installé VB.
Et pour transposer les différents programmes de tri en Python, j'ai eu affaire à :
* Java : je n'ai pas installé le Kit de développement
* C je n'ai pas installé C, j'avais déjà dev-C++, mais je ne m'en suis pas servi
* Pascal : je ne l'ai pas installé
* Pseudo-code : contrairement aux apparences, ça n'a pas été le plus facile (mal écrit)...

Donc, on peut -généralement- transposer d'un langage à un autre par "simple" lecture !
Toi tu trouves ton idée simple, je suis au regret de dire que -pour l'instant- je ne partage pas cet avis, au moins en ce qui concerne son écriture Python : tu as eu une idée très subtile, et elle te paraît tellement "évidente" que, tel l'arbre qui cache la forêt, tu n'as plus conscience de la complexité de la mise en oeuvre de ton algo...

@+

totomm · 03-09-2011 15:44:22

Bonjour,

Arrêtons ces petites phrases et ces sous-entendus qui peuvent toujours être retournés contre l'émetteur !

Puisque nous avons la chance d'avoir suffisamment de facultés et de bagages : Partageons nos résultats et confrontons nos raisonnements en toute bonne foi !

Post #1 : Mes commentaires étaient plutôt destinés comme aide-mémoire au "programmeur"
Post #6 : j'ai fait l'effort de commenter différemment pour expliquer a) La méthode en gros (lignes 47 à 52)
b) chacune des actions dans l'algorithme
Je supposais bien sûr connu que tout ce qui suit un # sur une ligne est un commentaire

Et donc je suis prêt à détailler ce qui serait encore obscur, mais qu'au moins je sois sûr que mon français des lignes 47 à 52 fait comprendre l'esprit de l'algorithme qui suit

@ yoshi : Les 32 5-combinaisons retenues sont listées par le programme DANS L'ORDRE où elles ont été retenues....
@ Freddy : Avant de passer en VB, j'avais demandé quel VBA et comment en relation avec SAS. En effet le VB 2008 de Microsoft utilise des "outils" dont comprendre l'utilisation est bien plus complexe que la même chose dans PYTHON...

@ tous : Je serais heureux si on pouvait justifier moins de 32, car je ne sais pas "démontrer" que 32 est LE minimum !
et si Freddy pouvait publier comment on montre "AU PLUS 36", ce serait profitable à tous.

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 !

totomm · 09-09-2011 08:45:44

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 surement mieux à publier !

A demain, peut-être, 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 11:33:06

Bonjour,

yoshi a écrit :

un trait d'humour freddyesque... que je n'ai d'ailleurs pas compris :-(

Mieux vaut ne pas comprendre....

yoshi a écrit :

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.

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 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

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 15:21:54

Bonjour,

Golgup a écrit :

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

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
   print "%3i" % L[j],
print
print
 
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
print
 
print "Matrice modifiée :"
for j in range(dim):
   if j%n==0 and j>0:
        print
    print "%3i" % L[j],
print

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 :

Matrice initiale :
 -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

@+

Forum de mathématiques - Bibm@th.net

#1 27-08-2011 09:37:01

Combinaisons de 12 nombres : triplets

#2 27-08-2011 17:14:05

Re : Combinaisons de 12 nombres : triplets

#3 28-08-2011 07:55:00

Re : Combinaisons de 12 nombres : triplets

#4 28-08-2011 14:02:03

Re : Combinaisons de 12 nombres : triplets

#5 28-08-2011 14:38:10

Re : Combinaisons de 12 nombres : triplets

#6 28-08-2011 17:20:06

Re : Combinaisons de 12 nombres : triplets

#7 31-08-2011 11:02:45

Re : Combinaisons de 12 nombres : triplets

#8 01-09-2011 09:24:15

Re : Combinaisons de 12 nombres : triplets

#9 01-09-2011 10:40:24

Re : Combinaisons de 12 nombres : triplets

#10 02-09-2011 10:01:00

Re : Combinaisons de 12 nombres : triplets

#11 02-09-2011 15:29:09

Re : Combinaisons de 12 nombres : triplets

#12 02-09-2011 17:10:00

Re : Combinaisons de 12 nombres : triplets

#13 02-09-2011 17:52:11

Re : Combinaisons de 12 nombres : triplets

#14 02-09-2011 17:54:00

Re : Combinaisons de 12 nombres : triplets

#15 02-09-2011 19:12:34

Re : Combinaisons de 12 nombres : triplets

#16 03-09-2011 15:44:22

Re : Combinaisons de 12 nombres : triplets

#17 08-09-2011 23:01:10

Re : Combinaisons de 12 nombres : triplets

#18 09-09-2011 08:45:44

Re : Combinaisons de 12 nombres : triplets

#19 09-09-2011 10:00:47

Re : Combinaisons de 12 nombres : triplets

#20 09-09-2011 11:33:06

Re : Combinaisons de 12 nombres : triplets

#21 09-09-2011 12:54:10

Re : Combinaisons de 12 nombres : triplets

#22 09-09-2011 14:28:18

Re : Combinaisons de 12 nombres : triplets

#23 09-09-2011 14:29:45

Re : Combinaisons de 12 nombres : triplets

#24 09-09-2011 15:21:54

Re : Combinaisons de 12 nombres : triplets

#25 09-09-2011 20:11:01

Re : Combinaisons de 12 nombres : triplets

Réponse rapide

Pied de page des forums