Forum de mathématiques - Bibm@th.net
Vous n'êtes pas identifié(e).
- Contributions : Récentes | Sans réponse
- Accueil
- » Entraide (supérieur)
- » analyse combinatoire
- » Répondre
Répondre
Résumé de la discussion (messages les plus récents en premier)
- yoshi
- 16-02-2016 11:57:57
Salut,
Intéressant ton prog, je me suis dit en le voyant qu'il était inutile effectivement de tout stocker...
Alors j'ai repris le mien :
#!/usr/bin/python
# -*- coding: utf-8 -*-
from itertools import combinations,permutations
L,nb,somme=[2,3,4,5,6,7,8],0,0
print("Ensemble des quintuplets de 5 chiffres : ")
for Q in combinations(L, 5):
print (Q)
for P in permutations(list(Q),5):
a,b,c,d,e=P
nb+=1
somme+=a*10000+b*1000+c*100+d*10+e
print ("\nNombre de nombres :",nb)
print ("\nSomme des nombres :",somme)
Je n'ai pas réfléchi pour voir si je peux encore réduire le code : si oui ce serait probablement au détriment de sa clarté...
Ce programme peut fonctionner - tel quel indifféremment - sur Windows, Mac OS ou Linux pourvu que vous utiulisiez une version de la branche 3.x de Python.
Sortie :
Ensemble des quintuplets de 5 chiffres :
(2, 3, 4, 5, 6)
(2, 3, 4, 5, 7)
(2, 3, 4, 5, 8)
(2, 3, 4, 6, 7)
(2, 3, 4, 6, 8)
(2, 3, 4, 7, 8)
(2, 3, 5, 6, 7)
(2, 3, 5, 6, 8)
(2, 3, 5, 7, 8)
(2, 3, 6, 7, 8)
(2, 4, 5, 6, 7)
(2, 4, 5, 6, 8)
(2, 4, 5, 7, 8)
(2, 4, 6, 7, 8)
(2, 5, 6, 7, 8)
(3, 4, 5, 6, 7)
(3, 4, 5, 6, 8)
(3, 4, 5, 7, 8)
(3, 4, 6, 7, 8)
(3, 5, 6, 7, 8)
(4, 5, 6, 7, 8)Nombre de nombres : 2520
Somme des nombres : 139998600
Je traite tout à la volée...
Je commence par générer (et afficher) chacun des 21 quintuplets Q de nombres.
Pour chaque quintuplet Q généré, je le transforme à la volée en liste sur la ligne for, pour générer un par un toutes les permutations P à partir de chacune.
Et je dois récupérer les nombres a,b,c,d,e de chaque permutation (générée sous forme de quintuplet) et :
* j'ajoute 1 à mon compteur
* j'ajoute le nombre composé [tex]\overline{abcde}[/tex] à ma variable somme
Une fois le traitement terminé, j'affiche le nombre de nombres et leur somme.
Les combinaisons et permutations sont obligatoirement générées, à partir de listes (objets voisins des tableaux des autres langages),sous forme de n-uplets.
Je pourrais me passer des lignes 7, 9, 12 et 15 et n'afficher que le résultat final.
Peut-être pourrais-je compacter encore mon code, mais ce serait au détriment de sa clarté.
Ce code fonctionnera indifféremment avec Windows, Mac OS ou Linux pour peu que vous ayez une version de la branche 3.x de Python d'installée...
@+
- freddy
- 16-02-2016 08:15:47
Salut,
astucieux, en effet. J'ai fait bêtement la même chose sous VBA, sans réfléchir plus avant ...
Le code liste tous les cas, ne retient que ceux dont on a besoin, et les écrit dans la première colonne, les lignes sont données par le compteur cpt.
Sub number()
Dim cpt, number As Double
cpt = 0
number = 0
For a = 2 To 8
For b = 2 To 8
If b = a Then GoTo finb
For c = 2 To 8
If c = b Or c = a Then GoTo finc
For d = 2 To 8
If d = c Or d = b Or d = a Then GoTo find
For e = 2 To 8
If e = d Or e = d Or e = c Or e = b Or e = a Then GoTo fine
cpt = cpt + 1
number = a * 10000 + b * 1000 + c * 100 + d * 10 + e
Cells(cpt, 1) = number
fine: Next e
find: Next d
finc: Next c
finb: Next b
Next aEnd Sub
- yoshi
- 15-02-2016 19:35:39
Re,
Bravo pour les programmeurs qui ont gagné haut la main
1. Ah mais non, rien de glorieux, c'est juste de la "bête" force brute !
2. C'était juste un pb d'addition, sauf si tu as fait [tex]2+3+4+5+6+7+8 = \frac{8\times 9}{2}-1[/tex]
3. Ça ne remet aucunement en cause le raisonnement (brillant, d'ailleurs) que - personnellement - je privilégie quand j'ai le temps...
4. Si tu ne sais pas programmer, cela ne t'incite pas à ajouter cette corde à ton arc ?
Si oui, je te recommande vivement Python qu'on qualifie souvent de "user friendly"
En Python, je peux calculer sur des nombres entiers dont la taille n'est limitée que par la qté de RAM de ta machine,
En Python, je peux calculer 1000 décimales si je veux en important un module spécifique...
Je pourrais en écrire des lignes des lignes encore...
@+
- Ostap Bender
- 15-02-2016 17:00:51
Ah oui.
On n'insistera pas assez sur l'apprentissage des tables de multiplication.
Bravo pour les programmeurs qui ont gagné haut la main.
Ostap Bender
- yoshi
- 15-02-2016 15:43:34
Ave Centurion,
Dès que j'ai 3 min (je ne sais pas quand :-)), je chercherai ce qui ne va pas chez Ostap
Mais :
Soit au total une somme égale à 11111N soit [tex]41\times271N= 41\times271\times11\times6\times5^2\times4\times3[/tex]
Oe encore [tex] 11111N=41\times271\times11\times6\times5^2\times4\times3 = 41\times271\times11\times 2\times 3 \times5^2\times 2^2 \times 3 = 2^3\times 3^2 \times 5^2\times 11 \times 41 \times 271[/tex]
Et
[tex]139998600 = 2^3 \times 3^2 \times 5^2 \times 7 \times 4 1\times 271[/tex]
L'écart vient du 7 au lieu de 11...
Donc du nombre N puisque 11111 = 41*271
Pourquoi ce 11 au lieu du 7 pas le temps de chercher...
Ah si ! Je l'ai:
2+3+4+5+6+7+8 = 35 = 5 * 7 et non 55 = 5 * 11
C'est tout bête !
@+
- freddy
- 15-02-2016 14:33:35
Re,
sur mon tableur, je sais que je les ai tous, la liste n'est pas si "grande" que cela, et j'ai bien regardé les premiers et les derniers, test visuel assez rapide.
Je peux donner mon code VBA, mais c'est assez facile à programmer quand on trouvé l'astuce.
Dès que j'ai 3 min (je ne sais pas quand :-)), je chercherai ce qui ne va pas chez Ostap, sauf s'il nous quoi avant ! ;-)
- yoshi
- 15-02-2016 11:56:47
Bonjour,
J'ai écrit le petit programme Python suivant :
A,B,K=[],[],[]
L=[2,3,4,5,6,7,8]
for T in combinations(L, 5):
A.append(list(T))
print("Ensemble des listes de 5 chifres : ")
for B in A:
print(B)
for T in permutations(B,5):
K.append(list(T))
print ("\nNombre de nombres :",len(K))
somme,nb=0,0
for C in K:
for i,a in enumerate(C):
nb+=a*10**(4-i)
somme+=nb
nb=0
print ("\nSomme des nombres :",somme)
Explications.
itertools est un module tout prêt de Python, j'en extrais les Classes permettant de calculer les combinaisons et les permutations.
combinaisons et permutations me sont données sous forme de n_uplets (ici, j'ai demandé des quintuplets).
Je construis la liste A des listes B de 5 chiffres...
(Parcourir des listes est plus rapide pour moi que de parcourir que de travailler sur des quintuplets)
Je charge et affiche ensuite chacune des listes de 5 chiffres
Pour chacune, j'extrais toutes les permutations de 5 chiffres sur 5, qui sont là aussi des quintuplets.
Je les stocke dans une liste K, sous forme chacune de liste à 5 éléments.
Reste à transformer chaque liste en le nombre voulu...
Via l'instruction enumerate, qui parcourt chaque liste chiffre après chiffre (désigné par a), et qui gère un compteur d'index, j'obtiens aussi l'index i du chiffre a extrait.
Comme il y a 5 chiffres, le 1er représente le nombre : [tex]a \times 10^{4-i}[/tex] (le 1er index en Python est 0)
Donc à chaque nouveau chiffre j'incrémente le nombre cherché de la valeur ci-dessus.
A chaque sortie de boucle, j'incrémente la somme du nombre nb, nombre que je remets à 0 ensuite.
Voilà ce que j'ai en lançant le script :
Ensemble des listes de 5 chiffres :
[2, 3, 4, 5, 6]
[2, 3, 4, 5, 7]
[2, 3, 4, 5, 8]
[2, 3, 4, 6, 7]
[2, 3, 4, 6, 8]
[2, 3, 4, 7, 8]
[2, 3, 5, 6, 7]
[2, 3, 5, 6, 8]
[2, 3, 5, 7, 8]
[2, 3, 6, 7, 8]
[2, 4, 5, 6, 7]
[2, 4, 5, 6, 8]
[2, 4, 5, 7, 8]
[2, 4, 6, 7, 8]
[2, 5, 6, 7, 8]
[3, 4, 5, 6, 7]
[3, 4, 5, 6, 8]
[3, 4, 5, 7, 8]
[3, 4, 6, 7, 8]
[3, 5, 6, 7, 8]
[4, 5, 6, 7, 8]Nombre de nombres : 2520
Somme des nombres : 139998600
S'il y a erreur, c'est que je fais la même interprétation de la question que freddy...
N-B :
[tex]41\times271\times7\times5^2\times2^2\times3^2 = 69999300[/tex]
Calcul Python :
>>> 41*271*7*(5**2)*(2**2)*(3**2)
69999300
>>>
** est la puissance en Python.
Faute de frappe, il faut remplacer[tex] 2^2[/tex] par [tex]2^3[/tex]
@+
- Ostap Bender
- 15-02-2016 10:05:52
Bonjour Freddy.
Allons bon ! Je ne trouve pas la même réponse.
J'ai [tex]7\times6\times5\times4\times3[/tex] lignes. Dans la première colonne, chacun des 7 chiffres apparait donc [tex]6\times5\times4\times3[/tex]. La somme des chiffres dans cette colonne est donc ce nombre d'occurrences multiplié par la somme [tex]2 + 3 + 4 + 5 + 6 + 7 + 8 = 55 = 5 \times 11 [/tex]. Reste à additionner ce nombre [tex]N = 11\times6\times5^2\times4\times3[/tex] à [tex]10N[/tex] obtenu dans la colonne des dizaines, à [tex]100N[/tex] obtenu dans la colonne des centaines, à ...
Soit au total une somme égale à [tex]11111N[/tex] soit [tex]41\times271N= 41\times271\times11\times6\times5^2\times4\times3[/tex].
Freddy trouve [tex]41\times271\times7\times5^2\times2^2\times3^2[/tex].
Qui pourra nous départager ?
Ostap Bender
- freddy
- 14-02-2016 20:33:56
Salut,
la somme est égale à 139 998 600, sauf erreur.
PS : comment ai-je fait ? Une feuille de calcul et un crayon électronique avec lequel j'ai écrit un petit programme VBA (qui m'a donné un peu à réfléchir, merci au passage ). Je n'ai pas vu, mais j'ai la vue qui baisse, le groupe cyclique (que je pensais réservé aux permutations, pas arrangements).
@yoshi : j'ai bien compris le message, mais j'ai toujours envie de comprendre. Je vais aussi tremper ma plume dans l'encre sympathique :-)
- Ostap Bender
- 12-02-2016 16:51:49
OK comme ça, Maître Yoshi, c'est clair.
Je vais donc continuer de faire de mon mieux.
Ostap Bender
- yoshi
- 12-02-2016 16:37:39
Re,
Il semble que je me sois mal fait comprendre - j'aurais peut-être dû m'abstenir - et j'en suis navré...
Je n'ai pas envie de justifier mes choix mathématiques/pédagogiques/didactiques dans toutes mes interventions.
(...) Je ne jette la pierre à personne.
Je ne crois pas avoir dit autre chose, je pensais mon intervention comme ayant été de nature à apaiser les tensions (si tensions, il y avait vraiment et non "chamaillerie" ) : en gros (et ça me plaît bien moins de le dire comme ça), je disais qu'il fallait te laisser intervenir comme tu l'entendais, que je ne souhaitais pas que quelqu'un revive mon expérience passée...
Relis-moi.
Mon bizuthage va continuer longtemps ?
No bizuthage at all !
@+
- Ostap Bender
- 12-02-2016 16:16:37
Maître Yoshi,
Je n'ai pas envie de justifier mes choix mathématiques/pédagogiques/didactiques dans toutes mes interventions.
Je revendique mon droit à l'erreur dans ces trois domaines auxquels j'adjoindrais la psychologie.
Je ne jette la pierre à personne. Je connais mon adresse à ce genre d'exercice :
je serais bien capable de me l'envoyer dans l'oeil et rien n'est plus désagréable.
Je croyais que les maths c'était gentil, que ça ne faisait de mal à personne. Je me trompe ?
Quant au contenu de mes interventions sur ce forum.
Si le public en veut, je les sors de ma hotte,
S'il n'en veut pas je les remets dans ma culotte.
Bon ça va comme ça ? On peut faire des maths ? Parce que c'est ce que je préfère !
Mon bizuthage va continuer longtemps ?
Ostap Bender
- yoshi
- 12-02-2016 15:49:06
Bonjour,
Yoshi, l'intervenant lambda (pas la même casquette), a eu suffisamment de démêlés par le passé avec le sieur totomm qui avait un peu trop tendance à "sauter sur tout ce qui bougeait", sans chercher assez à comprendre la motivation et le cheminement de la pensée dudit intervenant pour jeter la pierre aux procédés atypiques.
J'ai été, par le passé donc, suffisamment - souvent - atypique dans mon approche pour jeter la pierre aux autres... freddy s'est habitué.
Et il est vrai que beaucoup (trop) de ceux qui demandent de l'aide ont une rédaction assez elliptique obligeant à lire entre les lignes ou a rappeler les Règles de fonctionnement de notre forum qui exposent un niveau d'exigences pédagogiques pas vu ailleurs, où on se bouscule pour donner la (les) réponse(s) sans trop se préoccuper du "service" (?) éventuel qu'on leur rend ainsi.
Je suis allé tester ailleurs : je m'y suis rapidement fait traiter de "jeune branleur" par un habitué d'un niveau supérieur au mien (on trouve toujours facilement plus fort que soi) sans qu'aucun modo ne réagisse par un rappel à la courtoisie...
J'y avais signalé qu'un membre s'était fait pirater son compte. Réponse en substance : bien fait pour lui, la prochaine fois, il choisira un mot de passe plus costaud...
Mais revenons à nos moutons... Mon rôle de modo est de veiller à ce que tout reste "dans les clous" et que chacun soit tolérant envers l'autre : nul n'est parfait et personne ne peut se targuer de détenir LA vérité...
Cela dit, il n'est pas facile, à l'heure du zapping intensif qui caractérise l'époque actuelle, d'arriver à doser la répartition entre réponse pure et dure et explications pour amener le demandeur à comprendre de lui-même (ce qui lui sera bien plus profitable). Du haut de mes 10000 posts, je me fais parfois encore piéger et le je vois s'évaporer en un claquement de doigts, me laissant frustré de ne pas avoir pu aller au bout.
Je terminerais en paraphrasant Brassens :
Ne jetez pas la pierre au primo-intervenant atypique, (manque la bonne rime)
Je suis derrière...
@+
Yoshi
- modérateur -
- Ostap Bender
- 12-02-2016 10:34:26
D'accord. Je vais faire comme si Robinson ne revenait pas. D'ailleurs nous sommes vendredi.
Tu n'as peut-être pas remarqué les indications que j'ai écrites à l'encre sympathique, car il m'arrive d'être sympathique, sais-tu ?
Tu vas donc faire agir le groupe symétrique à 7 éléments sur ta feuille de calcul. Ainsi tu vas constater que les effectifs de chacun des chiffres de chaque colonnes sont égaux. A combien ? Il y a 7x6x5x4x3 = 2 520 lignes, donc chaque chiffre (il y en a 7) apparait 6x5x4x3 fois dans chaque colonne.
Nous sommes en vue du port, me semble-t-il.
Ostap Bender
SI j'ai demandé avec insistance le résultat de la première question c'est que
1/ Robinson donne l'impression qu'il l'a trouvé.
2/ Il serait idiot de partir sur des mauvaises bases comme un résultat non divisible par 7.
3/ J'ai toujours un a priori envers les intervenants qui ne font pas l'effort de traduire un énoncé. C'est pas bien d'avoir des principes, mais je suis comme ça. Maintenant si Robinson revient pour me dire que le français c'est sa troisième langue, qu'il a toujours eu un mal fou avec et que ce n'est pas la réforme de l'orthographe qui va arranger ça, je veux bien faire un effort pour comprendre...
- freddy
- 12-02-2016 09:56:19
Re,
Tu as raison, 7 chiffres. L'heure tardive, la fatigue et l'agacement contenu sont mauvais conseillers, je le vérifie une fois de plus.
On a donc 7!/2! = 7x6x5x4x3 = 2.520 nombres distincts possibles.
Voilà, tu as la réponse à ta première question.
Alors, la seconde ? Car bien entendu, on ne va pas faire le calcul bêtement à la main, comme tu le suggères, un brin ironique.
Et la solution ne me saute pas aux yeux, désolé. Et j'ai envie d'avoir la réponse, ça m’intéresse.
En attendant, le demandeur s'est barré, trouvant difficile de tomber sur une aide qui n'aide pas beaucoup, et qui renvoie la question que l'on a posé, comme un jokari :-)
Difficile de savoir doser la "bonne " réponse, celle qui donne envie de continuer à chercher, sans pour autant faire le boulot à la place des autres.
Par exemple, tu aurais pu supposer avoir la réponse à la première question est indiquer une piste pour répondre à la seconde.
Certains sont assez bon dans ce genre d’exercice, d'autres doivent encore apprendre.
Perso, je suis trop fatigué en ce moment pour chercher ...
A te lire, mon ami.